配点:5 点
問題文
N 给出一棵顶点树。树顶 它的编号为 1, 2, \cdots, N 并且i 第一条边是顶点 a_i 和顶点 连接 b_i 双向连接。
每个顶点都有 a, b 写入任意字符且顶点 i 中写入的字符是 c_i 。
0 如何删除多条边 2^{N-1} 有几种方法可以做到这一点,但其中之一是“删除边后,所有连接的组件都被删除” a, b 查找“包含两个字符”的个数,
请打印除以10^9+7 后的余数。
制約
- 2 \leq N \leq 100000
- c_i 是
给出了
a,b任何一个 - 1 \leq a_i, b_i \leq N
- 给定的图是一棵树
入力
输入是按以下格式从标准输入给出的。
N
c_1 c_2 \ldots c_N
a_1 b_1
\vdots
a_{N - 1} b_{N - 1}
出力
答案 将除以 10^9+7 后的余数打印在一行上。
入力例 1
7 b a b a b b a 2 1 3 7 3 2 3 4 5 4 4 6
出力例 1
4
要删除满足条件的边,请使用以下方法。 4 一。
- 不要删除任何边 删除
- 辺 (3, 2) 删除
- 辺 (3, 4) 删除
- 辺 (3, 2) 和边缘 (3, 4) 删除
入力例 2
2 a b 1 2
出力例 2
1
无法删除边。
入力例 3
22 b a b b a b b b a b a a a a b b a b b a a a 1 7 4 14 12 22 2 4 21 17 3 20 7 8 20 14 15 11 8 14 9 12 17 8 6 20 11 20 18 19 10 8 22 20 13 21 5 14 19 20 16 14
出力例 3
16