---

题意简述

给定一棵 $n$ 个节点的树，需要给每条边赋一个 $[0, 2^{30}-1]$ 的整数权值。
有 $q$ 条限制：每条限制 $(u, v, x)$ 表示 $u$ 到 $v$ 路径上所有边的权值异或和等于 $x$。
要求判断是否存在合法赋值，若存在，输出一种方案，使得所有边权异或和 $a_1 \oplus a_2 \oplus \dots \oplus a_{n-1}$ 最小。

---

核心转化

设 $p_i$ 表示从节点 $1$ 到节点 $i$ 的路径上所有边的异或和。
对于树上的任意两个节点 $u, v$，它们的路径异或为：

$$\text{xor}(u,v) = p_u \oplus p_v$$

这是因为从 $1$ 到 $\text{lca}(u,v)$ 的路径在 $p_u$ 和 $p_v$ 中分别出现一次，异或后抵消。

因此：

• 每条边 $(u,v)$ 的权值可以表示为 $a_{uv} = p_u \oplus p_v$。
• 给边赋权等价于给每个节点（除根外）赋 $p_i$。

---

条件图的建立

对每条限制 $(u, v, x)$，我们有：

$$p_u \oplus p_v = x$$

这可以看作在图 $G'$ 中连一条无向边 $(u, v)$，权值为 $x$。

若 $u$ 和 $v$ 在 $G'$ 中连通，则 $p_v$ 可由 $p_u$ 推导出来：

$$p_v = p_u \oplus (\text{路径异或})$$

---

可行性判断

对 $G'$ 的每个连通分量：

• 任选一个节点 $r$，设 $p_r = 0$，通过 BFS/DFS 求出分量内所有 $p_i$。
• 对分量内的每条边 $(u, v, x)$，检查 $p_u \oplus p_v$ 是否等于 $x$。

若某条边不满足，则无解。

---

最小化目标

目标：最小化 $S = a_1 \oplus a_2 \oplus \dots \oplus a_{n-1}$。

将 $a_i = p_{u_i} \oplus p_{v_i}$ 代入：

$$S = \bigoplus_{\text{edge } (u,v)} (p_u \oplus p_v) $$

在异或和中，$p_i$ 出现的次数等于节点 $i$ 在原树 $G$ 中的度数 $\deg(i)$。
因此：

$$S = \bigoplus_{i=1}^n \left( p_i \text{ 如果 } \deg(i) \text{ 是奇数，否则 } 0 \right) $$

即：

$$S = \bigoplus_{\deg(i) \text{ odd}} p_i$$

---

自由度的处理

设 $G'$ 有 $k$ 个连通分量，第 $j$ 个分量中任选一个代表 $r_j$，则分量内任意节点 $i$ 的 $p_i$ 可表示为：

$$p_i = p_{r_j} \oplus d_i$$

其中 $d_i$ 是已知常数（$d_{r_j} = 0$）。

于是：

$$S = \bigoplus_{j=1}^k \left( p_{r_j} \oplus \left( \bigoplus_{\substack{i \in \text{comp}_j \\ \deg(i) \text{ odd}}} d_i \right) \right) $$

记：

$$c_j = \bigoplus_{\substack{i \in \text{comp}_j \\ \deg(i) \text{ odd}}} d_i $$

则：

$$S = \bigoplus_{j=1}^k \left( p_{r_j} \oplus c_j \right) $$

---

分类讨论

• 若 $c_j = 0$ 对所有 $j$ 成立，则 $S = \bigoplus_{j=1}^k p_{r_j}$。

  • 若 $k = 0$，$S = 0$。
  • 若 $k > 0$，我们可以独立选择 $p_{r_j}$ 以最小化 $S$。
    由于 $S$ 是 $p_{r_j}$ 的异或，最小值为 $0$，只需让所有 $p_{r_j}$ 相等即可（例如全 $0$）。

• 若存在 $c_j \neq 0$，则 $S = \bigoplus_{j} (p_{r_j} \oplus c_j)$。
  设 $L$ 为满足 $c_j \neq 0$ 的 $j$ 集合。
  若 $|L|$ 为奇数，则 $S$ 恒非零，最小值为 $\bigoplus_{j \in L} c_j$（可通过适当调整 $p_{r_j}$ 实现）。
  若 $|L|$ 为偶数，可让 $S = 0$。

实际操作中，我们固定 $p_{r_1} = 0$，对每个 $j > 1$ 若 $j \in L$ 则设 $p_{r_j} = c_1 \oplus c_j$ 使 $S$ 最小。

---

算法步骤

1. 读入树 $G$，计算每个节点的度数 $\deg(i)$。
2. 建立图 $G'$：对每个限制 $(u, v, x)$，在 $u$ 和 $v$ 间加无向边权 $x$。
3. 对 $G'$ 的每个连通分量：
   • 任选代表 $r$，设 $p_r = 0$，BFS 求分量内所有 $p_i$。
   • 检查分量内边权是否一致。
4. 若检查失败，输出 "No"。
5. 否则，计算 $c_j = \bigoplus_{\substack{i \in \text{comp}_j \\ \deg(i) \text{ odd}}} d_i$。
6. 选择 $p_{r_j}$ 使 $S$ 最小。
7. 根据 $p_i$ 计算边权 $a_{uv} = p_u \oplus p_v$ 并输出。

---

复杂度

• 时间复杂度：$O(n + q)$（若使用位运算优化，也可 $O((n+q)\log X)$ 通过）
• 空间复杂度：$O(n + q)$

---

这样，我们就能在满足条件的前提下，最小化所有边权的异或和。