#abc222e. [abc222_e]Red and Blue Tree
[abc222_e]Red and Blue Tree
問題文
頂点の木と、長さ の数列 、整数 が与えられます。
木の頂点には から の番号がつけられており、 番目の辺は頂点 と を結んでいます。
この木の 個の辺をそれぞれ赤か青のどちらかに塗ります。そのような方法は 通りありますが、そのうち次の条件を満たすような塗り方の個数を で割った余りを求めてください。
条件:
最初、駒を頂点 におく。 の順に、駒を頂点 から頂点 まで、辺をたどって最短経路で動かす。 これらの操作を最後まで行ったとき、赤く塗られた辺を通過した回数を 、青く塗られた辺を通過した回数を とすると、 である。
制約
- 与えられるグラフは木である
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入力例 1
出力例 1
番目の辺を赤く、 番目の辺を青く塗ったとき、
- 頂点 から頂点 への移動で赤い辺を 回、青い辺を 回
- 頂点 から頂点 への移動で赤い辺を 回、青い辺を 回
- 頂点 から頂点 への移動で赤い辺を 回、青い辺を 回
- 頂点 から頂点 への移動で赤い辺を 回、青い辺を 回
それぞれ通過し、全体では赤い辺を 回、青い辺を 回通るため、条件を満たします。
この他、 番目の辺を青く、 番目の辺を赤く塗るときも条件を満たし、これら以外の塗り方は条件を満たさないため、答えは 通りです。
入力例 2
出力例 2
条件を満たす塗り方が存在しないこともあります。