Ad-hoc Master 题解

Coffee_zzz · 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。

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