P17304 [ICPC 2026 Xi'an I] XOR and LCA

Yuki 有一棵包含 $2^n$ 个结点的树，结点的编号为 $0$ 至 $2^n - 1$，第 $i$ 条边连接结点 $u_i$ 与结点 $v_i$。 设 $\operatorname{lca}_{r}(u, v)$ 表示，以结点 $r$ 为根时，结点 $u$ 与结点 $v$ 的最近公共祖先。你需要帮助 Yuki 求出： $$ \bigoplus_{0 \le u < v < 2^n} \operatorname{lca}_{u \oplus v}(u, v) $$ 其中 $\oplus$ 表示按位异或运算。

本题包含多组测试数据。 第一行包含一个正整数 $t$ $(1 \le t \le 10^4)$，表示测试数据组数。 对于每组测试数据： - 第一行包含一个正整数 $n$ $(1 \le n \le 21)$。 - 接下来 $2^n - 1$ 行，第 $i$ 行包含两个正整数 $u_i, v_i$ $(0 \le u_i, v_i < 2^n,\ u_i \ne v_i)$。 保证输入数据形成一棵树，保证所有测试数据中 $2^n$ 的总和不超过 $2^{21}$。

对于每组测试数据，输出一行，包含一个整数，表示答案。

对于第 $1$ 组测试数据： - 以结点 $1$ 为根时，结点 $0$ 与结点 $1$ 的最近公共祖先为结点 $1$，因此答案为 $\operatorname{lca}_1(0, 1) = 1$。 对于第 $2$ 组测试数据： - 我们计算所有点对 $(u, v)$ 的 $\operatorname{lca}_{u \oplus v}(u, v)$： - $(0, 1)$：$0 \oplus 1 = 1$，$\operatorname{lca}_1(0, 1) = 1$。 - $(0, 2)$：$0 \oplus 2 = 2$，$\operatorname{lca}_2(0, 2) = 2$。 - $(0, 3)$：$0 \oplus 3 = 3$，$\operatorname{lca}_3(0, 3) = 3$。 - $(1, 2)$：$1 \oplus 2 = 3$，$\operatorname{lca}_3(1, 2) = 2$。 - $(1, 3)$：$1 \oplus 3 = 2$，$\operatorname{lca}_2(1, 3) = 2$。 - $(2, 3)$：$2 \oplus 3 = 1$，$\operatorname{lca}_1(2, 3) = 2$。 - 异或和为 $1 \oplus 2 \oplus 3 \oplus 2 \oplus 2 \oplus 2 = 2$。