/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
N 頂点の木が与えられます。ここで、N は 奇数 です。 木の頂点には 1 から N までの、辺には 1 から N-1 までの番号が付けられています。 辺 i は頂点 u_i, v_i を結び、初期状態での重みは w^1_i です。
あなたは、次の操作を何度でも行えます。
- 木から辺 (u, v) を選ぶ。この辺の現在の重みが w であるとする。u, v のいずれかちょうど一方に接続する各辺について、その重みを w との XOR に置き換える（操作前の辺の重みが 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
Score : 800 points
Problem Statement
You are given a tree with N vertices, where N is odd. The vertices are numbered from 1 through N and edges from 1 through N-1. The edge i connects vertices u_i and v_i and its initial weight is w^1_i.
You can perform the following operation any number of times:
- Choose an edge (u, v) of the tree, and suppose that its weight now is w. For every edge, which is incident to exactly one of u and v, we XOR the weight of that edge with w (if it was w_1, replace it with w_1 \oplus w).
Your goal is to reach the state where each edge i has weight w^2_i. Determine if you can get to the goal by performing the operation above any number of times.
Constraints
- 1 \le N \le 10^5
- N is odd.
- 1\le u_i, v_i \le N
- u_i \neq v_i
- 0\le w^1_i, w^2_i < 2^{30}
- All values in input are integers.
- The input represents a valid tree.
Input
Input is given from Standard Input in the following format:
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}
Output
If you can get the goal weight assignment from the initial state, output YES. Otherwise, output NO.
Note that the checker is case-insensitive: you can print letters in both uppercase and lowercase.
Sample Input 1
3 1 2 1 1 2 3 8 9
Sample Output 1
YES
If you perform the operation on the edge 1, the weight of the edge 2 becomes 8 \oplus 1=9.
Sample Input 2
5 1 2 0 3 1 3 1 0 1 4 2 1 1 5 0 0
Sample Output 2
NO