分数: 800 点
问题陈述
你得到了一棵树 N 顶点,其中 N is 奇数。 顶点编号从 1 通过 N 和边缘 1 通过 N-1。 边缘 i 连接顶点 u_i 和 v_i 其初始权重为 w^1_i.
您可以执行以下操作任意次:
- 选择一条边 树的 (u, v) ,并假设它现在的重量是 w。对于每条边,恰好与其中之一相关 u 和 v,我们 异或 该边的权重 w (如果是 w_1,替换为 w_1 \oplus w).
你的目标是达到每条边 i 有重量 w^2_i。 确定是否可以通过执行上述操作任意次数来达到目标。
约束
- 1 \le N \le 10^5
- N 是奇数。
- 1\le u_i, v_i \le N
- u_i \neq v_i
- 0\le w^1_i, w^2_i < 2^{30}
- 输入中的所有值都是整数。
- 输入代表一棵有效的树。
输入
输入由标准输入按以下格式给出:
N
u_1 v_1 w^1_1 w^2_1
u_2 v_2 w^1_2 w^2_2
\vdots
u_{N-1} v_{N-1} w^1_{N-1} w^2_{N-1}
输出
如果可以从初始状态得到目标权重分配,则输出 YES。否则,输出 NO。
请注意,检查器不区分大小写:您可以打印大写和小写字母。
示例输入 1
3 1 2 1 1 2 3 8 9
示例输出 1
YES
如果在边缘执行操作 1,边的权重 2 变为 8 \oplus 1=9.
示例输入 2
5 1 2 0 3 1 3 1 0 1 4 2 1 1 5 0 0
示例输出 2
NO