XOR Tree

### 题目描述 给一棵有 $N$ 个节点的树，节点编号从 $0$ 到 $N-1$， 树边编号从 $1$ 到 $N-1$。第 $i$ 条边连接节点 $x_i$ 和 $y_i$，其权值为 $a_i$。 你可以对树执行任意次操作，每次操作选取一条链和一个非负整数 $x$，将链上的边的权值与 $x$ 异或成为该边的新权值。 问最少需要多少次操作，使得所有边的权值都为 $0$。 ### 输入格式 第一行有 $1$ 个整数，代表树的节点数 $N$。 接下来 $N-1$ 行，每行有 $3$ 个整数，第 $i+1$ 行上的整数分别代表第 $i$ 条边的参数 $x_i,y_i,a_i$。 ### 输出格式 仅一行 $1$ 个整数，即最小操作数。 ### 数据范围与说明 - $2\leq N \leq 10^5$ - $0\leq x_i,y_i \leq N-1$ - $0\leq a_i \leq 15$ - 保证给定的图是一棵树 - 保证输入数据都是整数

[problemUrl]: https://atcoder.jp/contests/apc001/tasks/apc001_f $ N $ 頂点の木が与えられます。頂点には $ 0 $ から $ N-1 $ の番号がついています。 辺は $ 1 $ から $ N-1 $ までの番号がついていて、辺 $ i $ は頂点 $ x_i $ と $ y_i $ をつなぎ、また $ a_i $ という値を保持しています。 あなたは以下の操作を何回でもすることが出来ます: - ある単純pathとある非負整数 $ x $ を選び、そのpathを構成する各辺 $ e $ について、 $ a_e\ ←\ a_e\ ⊕\ x $ (⊕ は xor)と変化させる。 目標はすべての辺 $ e $ について $ a_e\ =\ 0 $ とすることです。 目標を達成するために必要な最小の操作回数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ y_1 $ $ a_1 $ $ x_2 $ $ y_2 $ $ a_2 $ $ : $ $ x_{N-1} $ $ y_{N-1} $ $ a_{N-1} $

目標を達成するために必要な操作回数の最小値を出力せよ。

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

3

2
1 0 0

0

### 制約 - $ 2\ <\ =\ N\ <\ =\ 10^5 $ - $ 0\ <\ =\ x_i,y_i\ <\ =\ N-1 $ - $ 0\ <\ =\ a_i\ <\ =\ 15 $ - 与えられるグラフは木 - 入力は全て整数 ### Sample Explanation 1 以下のようにして三回で目標を達成できます。 - まず、頂点 $ 1,2 $ を結ぶ path に対して $ x=1 $ で操作する - 次に、頂点 $ 2,3 $ を結ぶ path に対して $ x=2 $ で操作する - 最後に、頂点 $ 0,4 $ を結ぶ path に対して $ x=4 $ で操作する