← 返回题目列表

AtCoder · typical90_bu

073. 我们需要a和b(★5)

中文机器翻译题面 查看原题

配点: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