题解：P4672 [BalticOI 2011] Tree Mirroring (Day2)

Monomial · 2025-04-13 21:46:19 · 题解

有趣思维题。

找根判定看上去不太好做，我们考虑找叶子判定。

如果我们已经有了一个叶子，那么直接 01bfs，如果这个叶子到一个点有两条边不交的最短路（在 bfs 时表现为被松弛两次），那么在图合法的情况下，这个点必定也是一个叶子。接下来我们只需判定剩下的是否是两个连通块并且它们是否同构即可。这个条件是充要的。

稍微困难一点的是之前这个找叶子的过程，这个需要一点观察，下图是一个示例，其中 3,4 是原树的叶子，假设点 1,6 向外面有边。

我们观察 3,4 两个点的性质。容易发现其为一条其中点均满足 deg=2 的极长链的中点。实际上对于所有合法图中的叶子节点，由对称性可得这个条件都是满足的。

那么我们直接找一条这样的链，就一定能找到叶子吗？并不是，考虑如下情形（原树的一部分）。

其中 2,3,4 这 3 个点构成了一条 deg=2 的极长链，其中 3 为中点，但 3 并不是一个叶子。所以我们需要更强的判定。

假设极长链的两个端点向外分别和 u,v 有边，我们声称在合法情况下，至少有一个无序二元组 (u,v) 出现了 \geq 2 次，这时符合条件的极长链的中点均为叶子。

考虑反证。我们假设有 e 条链，每条链对应的无序二元组为 (u_{i},v_{i})，在原树中简化为 p_{i}，其互不相同。由于 p_{i} 不在链上，那么 deg_{p_{i}} > 2。所以除去这些叶子对 p_{i} 的贡献 1，剩下的贡献和应当 \geq 2e。而我们考虑最优的造成贡献的方式只有每次合并两个 p_{i} 的连通块，这里只会合并 e-1 次，每次对合并的两个分别造成 1 的贡献，总贡献就是 2e-2 < 2e，所以我们之前提出的结论是成立的。

我们刚刚的这个做法是基于第一个图中 1,6 向外面有边，对于无边的情况，即原图为一个环，那么树的形态应当是一条链，直接特判即可。

那么我们整道题的做法即为，先拉出所有 deg=2 的极长链，然后用 (u,v) 判定找叶子，搜出所有叶子，树同构判定（注意不合法情况可能有环，要特殊处理）。代码很好写，实现优秀可以做到 \mathcal{O}(n+m)。