073 - We Need Both a and b（★5）
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点：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