← 返回题目列表

AtCoder · agc052_b

B. 树边缘异或

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

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