← 返回题目列表

AtCoder · agc050_f

F. NAND 树

中文机器翻译题面 查看原题

分数: 2000 点

问题陈述

有一棵树,其顶点标记为 0 or 1。 这棵树有 N 顶点编号 1 通过 N。 对于每个 i,有一条边连接 Vertex a_i 和顶点 b_i。 顶点的标签 i is c_i.

Snuke 想要在树上重复执行以下操作:

  • 选择一条边,将其收缩,并用两个旧顶点标签的 NAND 来标记新顶点。

执行后 N - 1 操作,树最终只有一个顶点。 其中 (N-1)! 这样做的方法,有多少会导致顶点标记为 1? 计算答案 模数 2.

注释

  • NAND操作定义如下: NAND(0, 0) = NAND(0, 1) = NAND(1, 0) = 1, NAND(1, 1) = 0.
  • 当我们收缩 Vertex 之间的边时 s 和顶点 t,我们删除边,并同时合并两个顶点。 合并后的顶点与顶点之间有一条边 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

事实证明,在 4 全部 6 最终标签的方式 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