配点 : $2000$ 点

問題文

各頂点に $0$ または $1$ が書かれた木があります。 この木は $N$ 個の頂点を持ち、それらには $1$ から $N$ までの番号が振られています。 各 $i$ について、頂点 $a_i$ と頂点 $b_i$ を結ぶ辺が存在します。 頂点 $i$ に書かれた数は $c_i$ です。

すぬけ君は、この木に以下の操作を繰り返します。

• 辺を $1$ 本選んで縮約し、消された $2$ 個の頂点に書かれていた数の NAND を新たな頂点に書き込む。

$N - 1$ 回の操作後、木は $1$ 個の頂点となります。 このような操作の行い方は $(N-1)!$ 通りありますが、そのうち最後の頂点に $1$ が書き込まれるものは何通りあるでしょうか。 この答えを 2 で割った余りを計算してください。

注記

• 演算 NAND の定義は次の通りです: $NAND(0, 0) = NAND(0, 1) = NAND(1, 0) = 1, NAND(1, 1) = 0$.
• 頂点 $s$ と頂点 $t$ を結ぶ辺を縮約する際は、その辺を取り除くと同時に $2$ 頂点を併合します。 縮約後の木において、併合により生まれた頂点と頂点 $u$ を結ぶ辺が存在するのは、縮約前の木において $s$ と $u$ を結ぶ辺または $t$ と $u$ を結ぶ辺が存在するときであり、またそのときに限られます。

制約

• $2 \leq N \leq 300$
• $1 \leq a_i < b_i \leq N$
• 入力が表すグラフは木である。
• $0 \leq c_i \leq 1$
• 入力中の全ての値は整数である。

入力

入力は標準入力から以下の形式で与えられる。

$N$

$a_1$ $b_1$

$:$

$a_{N-1}$ $b_{N-1}$

$c_1$ $c_2$ $\cdots$ $c_N$

出力

答えを出力せよ。

4
1 2
2 3
2 4
0 1 1 0

0

$6$ 通りの操作順のうち $4$ 通りで最後の頂点に $1$ が書き込まれることがわかります。よって、答えは $4 \ mod \ 2 = 0$ です。

4
1 2
2 3
3 4
1 1 0 1

1

20
3 15
1 12
10 16
3 19
5 20
1 9
6 13
14 19
2 4
8 11
12 16
6 20
2 17
16 18
17 19
7 10
16 20
2 20
8 20
1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0

0