#P13057. [AGC052B] Tree Edges XOR

[AGC052B] Tree Edges XOR

题目描述

给定一棵包含 NN 个结点的树,其中 NN 为奇数。结点编号为 11 到 NN,边编号为 11 到 N−1N-1。第 ii 条边连接结点 uiu_i 和 viv_i,且具有两个整数权值:初始权值 wi,1w_{i,1} 和目标权值 wi,2w_{i,2}。

你可以执行任意多次(包括零次)以下操作:

  • 选择一条边 (u,v)(u,v),当前权值为 ww。将所有恰与 u,vu,v 中一个点相连的边的权值异或上 ww(不包括 (u,v)(u,v) 这条边本身)。

判断能否通过执行上述操作(任意顺序,任意次数),使得对于每一条边 ii,其权值从初始的 wi,1w_{i,1} 变为目标值 wi,2w_{i,2}。

输入格式

第一行一个正整数 NN,表示树的结点个数。

下面 N−1N-1 行,每行四个非负整数 ui,vi,wi,1,wi,2u_i,v_i,w_{i,1},w_{i,2},表示树上的一条边。

输出格式

如果有可能通过操作使所有边的权值变为目标值,输出一行 YES;否则输出一行 NO。

输入输出样例 #1

输入 #1

3
1 2 1 1
2 3 8 9

输出 #1

YES

输入输出样例 #2

输入 #2

5
1 2 0 3
1 3 1 0
1 4 2 1
1 5 0 0

输出 #2

NO

说明/提示

样例一解释

如果操作边 (1,2)(1,2),那么边 (2,3)(2,3) 的权值会变成 8⊕1=98\oplus 1=9。

数据范围

  • 1≤N≤1051 \le N \le 10^5
  • 1≤ui,vi≤N1 \le u_i, v_i \le N (保证输入构成一棵树)
  • 0≤wi,1<2300 \le w_{i,1} < 2^{30}
  • 0≤wi,2<2300 \le w_{i,2} < 2^{30}