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

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #2

2
1 0 0

样例输出 #2

0

提示

制約

• $2\ <\ =\ N\ <\ =\ 10^5$
• $0\ <\ =\ x_i,y_i\ <\ =\ N-1$
• $0\ <\ =\ a_i\ <\ =\ 15$