题目描述

$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}$

输出格式

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

题目大意

题目描述

给一棵有 $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$
• 保证给定的图是一棵树
• 保证输入数据都是整数

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$ で操作する