配点 : $1000$ 点

問題文

$N$ 頂点の木が与えられます。頂点には $0$ から $N-1$ の番号がついています。 辺は $1$ から $N-1$ までの番号がついていて、辺 $i$ は頂点 $x_i$ と $y_i$ をつなぎ、また $a_i$ という値を保持しています。 あなたは以下の操作を何回でもすることが出来ます:

• ある単純pathとある非負整数 $x$ を選び、そのpathを構成する各辺 $e$ について、 $a_e \gets a_e \oplus x$ (⊕ は xor)と変化させる。

目標はすべての辺 $e$ について $a_e = 0$ とすることです。 目標を達成するために必要な最小の操作回数を求めてください。

制約

• $2 \leq N \leq 10^5$
• $0 \leq x_i,y_i \leq N-1$
• $0 \leq a_i \leq 15$
• 与えられるグラフは木
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$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

以下のようにして三回で目標を達成できます。

• まず、頂点 $1,2$ を結ぶ path に対して $x=1$ で操作する
• 次に、頂点 $2,3$ を結ぶ path に対して $x=2$ で操作する
• 最後に、頂点 $0,4$ を結ぶ path に対して $x=4$ で操作する

2
1 0 0

0