P17267 [ICPC 2017 Urumqi R] A Possible Tree

Alice 知道 Bob 有一棵秘密的树（图论意义上的树），包含 $n$ 个节点和 $n - 1$ 条带权边，边权为 $[0, 2^{60} - 1]$ 内的整数。她知道树的结构，但不知道边权的具体信息。 多亏 Bob 良心发现，Alice 得到了 $m$ 条关于这棵树的结论。每条结论给出三个整数 $u, v$ 和 $val$，表示 $u$ 和 $v$ 之间唯一的最短路径上所有边权的 **异或和（XOR）** 等于 $val$。 给出的结论中可能存在错误，Alice 希望找出最大的整数 $W$，使得前 $W$ 条结论是兼容的。也就是说，至少存在一种边权分配方案能同时满足前 $W$ 条结论，但无法同时满足前 $W + 1$ 条结论（或者总共只给出了 $W$ 条结论）。 请帮助 Alice 求出 $W$ 的确切值。

输入包含多组测试数据，第一行包含一个整数 $t$ ($1 \le t \le 5$)，表示测试数据的组数。请注意，原题 $t=30$，洛谷上拆为了 $6$ 个测试点评测。 对于每组数据，第一行包含两个整数 $n$ ($1 \le n \le 100000$) 和 $c$ ($1 \le c \le 100000$)，分别表示树的节点数量以及给出的结论数量。接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示树中连接第 $u$ 个节点和第 $v$ 个节点的一条边。接下来的 $c$ 行，每行提供一条结论，包含三个整数 $u$、$v$ 和 $val$，其中 $1 \le u, v \le n$，$val \in [0, 2^{60} - 1]$。

对于每组测试数据，输出一行一个整数 $W$。

翻译由 DeepSeek V4 Pro 完成