自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

搬运于2025-08-24 23:01:55，当前版本为作者最后更新于2024-08-10 18:35:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到，将所有 $\operatorname{dis}$ 为 $k$ 的信息异或起来可以得到所有深度为 $k$ 的结点的权值的异或和 $(2 \le k \le h)$，因为在满二叉树中，对于某个满足 $dep_u=k$ 的结点 $u$，满足 $\operatorname{dis}(u,v)=k$ 的结点 $v$ 的数量为奇数，而对于某个满足 $dep_u\ne k$ 的结点 $u$，满足 $\operatorname{dis}(u,v)=k$ 的结点 $v$ 的数量为偶数。证明显然。

于是我们可以得到，对于所有满足 $2\le k \le h$ 的整数 $k$，深度为 $k$ 的结点的权值的异或和，这恰恰是根结点的信息。枚举一下，找到恰好能匹配上的点即为满足条件的根结点。

再求根结点的权值。我们可以先求出所有点的权值的异或和，再异或上根结点的所有信息，得到根结点的权值。

再次注意到，如果两个点的距离为奇数，那么将两个点中所有满足 $\operatorname{dis}$ 为奇数的信息异或起来就能得到所有点的权值的异或和。如果两个点的距离为偶数，则异或起来会得到 $0$。

那我们任选一个点，枚举剩下的点，按照上述方法求出异或和。注意如果得到的全是 $0$，那么其实所有点的权值的异或和就是 $0$。

于是我们就可以求出根节点的编号和根结点的权值了。