You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Y 的朋友小 A 有一片白桦树森林，森林中的每棵白桦树都可以抽象成一棵无根树。

对于一棵含有 $n$ 个节点的树，它由 $n-1$ 条无向边组成，且任意两个节点之间恰好存在一条简单路径。

这棵树上的每一条边都有一个“积雪度”，可以用一个非负整数表示，小 Y 可以进行如下操作若干次：

• 选择两个不同的节点 $u,v$，以及一个非负整数 $x$，对树上 $u$ 到 $v$ 的简单路径上的每条边，将其积雪度与 $x$ 进行按位异或。

现在小 A 给了小 Y 森林中的 $q$ 棵树，小 Y 请你帮她对每棵树算出：至少要进行多少次操作，才能让每条边的积雪度都变成 $0$。

输入格式

从文件 snow.in 中读入数据。

第一行一个整数 $q$，表示树的数量。

接下来依次输入 $q$ 棵树，对于每棵树：

• 第一行一个整数 $n$，表示这棵树的节点数量。
• 第 $i+1$（$1\le i\le n-1$）行三个整数，$u_i,v_i,w_i$ 表示树的第 $i$ 条边的两个端点，以及这条边的积雪度。

输出格式

输出到文件 snow.out 中。

输出 $q$ 行，第 $i$（$1\le i\le q$）行输出一个整数表示至少要进行多少次操作，才能让第 $i$ 棵树的每条边积雪度都变成 $0$。

样例 1 输入

2
3
1 2 1
1 3 2
4
1 2 1
2 3 3
3 4 2

样例 1 输出

2
2

样例 1 解释

对于第一棵树：给节点 $1,2$ 之间的路径积雪度异或 $1$，再给节点 $1,3$ 之间的路径积雪度异或 $2$ 即可。

对于第二棵树：给节点 $1,3$ 之间的路径积雪度异或 $1$，再给节点 $2,4$ 之间的路径积雪度异或 $2$ 即可。

样例 2

见选手目录下的 snow/snow2.in 与 snow/snow2.ans。

该样例满足子任务 $1$ 的约束条件。

样例 3

见选手目录下的 snow/snow3.in 与 snow/snow3.ans。

该样例满足子任务 $2$ 的约束条件。

样例 4

见选手目录下的 snow/snow4.in 与 snow/snow4.ans。

该样例满足子任务 $3$ 的约束条件。

样例 5

见选手目录下的 snow/snow5.in 与 snow/snow5.ans。

该样例满足子任务 $4$ 的约束条件。

样例 6

见选手目录下的 snow/snow6.in 与 snow/snow6.ans。

该样例满足子任务 $5$ 的约束条件。

样例 7

见选手目录下的 snow/snow7.in 与 snow/snow7.ans。

该样例满足子任务 $6$ 的约束条件。

样例 8

见选手目录下的 snow/snow8.in 与 snow/snow8.ans。

该样例满足子任务 $7$ 的约束条件。

数据范围

对于所有测试数据，保证 $1\le q\le 50$，对于每棵树 $1\le n\le 10^5$，$0\le w_i\le 31$，并且输入的 $n-1$ 条边构成树。

记 $N$ 为 $q$ 棵树的节点数之和，保证 $N\le 10^5$。

特殊性质 A：对于每棵树，$w_1,w_2,\dots,w_{n-1}$ 全部相同。 特殊性质 B：对于每棵树，$w_1,w_2,\dots,w_{n-1}$ 中至多有 $2$ 种不同的值。 特殊性质 C：对于每棵树，其所有边权均满足 $w_i\le 15$。

本题开启所有合理的子任务依赖。