F - NAND Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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

出力

答えを出力せよ。

入力例 1

4
1 2
2 3
2 4
0 1 1 0

出力例 1

0

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

入力例 2

4
1 2
2 3
3 4
1 1 0 1

出力例 2

1

入力例 3

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

出力例 3

0

Score : 2000 points

Problem Statement

There is a tree whose vertices are labelled with either 0 or 1. The tree has N vertices numbered 1 through N. For each i, there is an edge connecting Vertex a_i and Vertex b_i. The label of Vertex i is c_i.

Snuke wants to repeat performing the following operation on the tree:

  • Choose an edge, contract it, and label the new vertex with the NAND of the labels of two old vertices.

After performing N - 1 operations, the tree ends up with a single vertex. Among (N-1)! ways to do so, how many will result in a vertex labelled with 1? Compute the answer modulo 2.

Notes

  • NAND operation is defined as follows: NAND(0, 0) = NAND(0, 1) = NAND(1, 0) = 1, NAND(1, 1) = 0.
  • When we contract an edge between Vertex s and Vertex t, we remove the edge, and simultaneously merge the two vertices. There is an edge between the merged vertex and Vertex u in the new tree iff there is an edge between s and u, or an edge between t and u, in the old tree.

Constraints

  • 2 \leq N \leq 300
  • 1 \leq a_i < b_i \leq N
  • The input represents a valid tree.
  • 0 \leq c_i \leq 1
  • All values in the input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

4
1 2
2 3
2 4
0 1 1 0

Sample Output 1

0

It turns out that in 4 of all 6 ways the final label will be 1, so the answer is 4 \ mod \ 2 = 0.

Sample Input 2

4
1 2
2 3
3 4
1 1 0 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

0