题目描述

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

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

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

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

输入格式

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

$N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $c_1$ $c_2$ $\cdots$ $c_N$

输出格式

答えを出力せよ。

题目大意

一个 $n$ 个点的树。每个点有点权 $0$ 或 $1$。

每次可以选择一条边，使两个端点缩成一个点，新点权值为两端点权值 AND 再取反。

一直操作直到只剩一个点。

求有多少种操作方案使最终剩下的点权值为 $1$。输出答案对 $2$ 取模的值。

4
1 2
2 3
2 4
0 1 1 0

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

提示

注記

• 演算 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$
• 入力中の全ての値は整数である。

Sample Explanation 1

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