CF1788F XOR, Tree, and Queries

给定一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。 你需要为每条边分配一个权值。第 $i$ 条边的权值为 $a_i$（$1 \leq i \leq n-1$）。每条边的权值必须是 $0$ 到 $2^{30}-1$ 之间的整数（包含两端）。 你还会得到 $q$ 个条件。每个条件由三个整数 $u$、$v$ 和 $x$ 组成，表示从 $u$ 到 $v$ 的最短路径上所有边的权值的按位异或（bitwise XOR）为 $x$。 请判断是否存在一组 $a_1, a_2, \ldots, a_{n-1}$ 满足所有给定条件。如果存在，请输出一组解，使得 $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ 的值最小。这里，$\oplus$ 表示按位异或操作。 如果有多组解使得 $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ 最小，输出任意一组即可。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 2.5 \cdot 10^5$，$0 \le q \le 2.5 \cdot 10^5$）。 接下来的 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \neq y_i$），表示第 $i$ 条边连接顶点 $x_i$ 和 $y_i$。 保证给定的边构成一棵树。 接下来的 $q$ 行，每行包含三个整数 $u$、$v$ 和 $x$（$1 \le u, v \le n$，$u \neq v$，$0 \le x \le 2^{30}-1$），表示从 $u$ 到 $v$ 的最短路径上所有边的权值的按位异或为 $x$。

如果不存在满足条件的 $a_1, a_2, \ldots, a_{n-1}$，输出 "No"。 否则，第一行输出 "Yes"。 第二行输出 $n-1$ 个整数，第 $i$ 个整数为第 $i$ 条边的权值。如果有多组解满足条件且 $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$ 最小，输出任意一组即可。 输出 "Yes" 或 "No" 时，大小写不敏感。例如，"yEs"、"yes"、"Yes"、"YES" 都会被识别为肯定回答。

对于第一个样例，不存在一组边权满足所有条件。 对于第二个样例，两个条件分别为 $a_1 \oplus a_2 \oplus a_3=2$ 和 $a_4 \oplus a_5=7$。存在多组解，例如 $(a_1, a_2, a_3, a_4, a_5)=(1, 2, 1, 4, 3)$。 对于第三个样例，两个条件分别为 $a_1 \oplus a_2 \oplus a_3=3$ 和 $a_1 \oplus a_4 \oplus a_5=5$。存在多组解满足条件。 $(a_1, a_2, a_3, a_4, a_5)=(1, 1, 3, 4, 0)$ 满足条件，但所有边权的异或和为 $7$，不是最小的 $a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$，因此不能作为答案。 由 ChatGPT 4.1 翻译