分数: 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