题解：P6697 [BalticOI 2020] 村庄 (Day2)

· · 题解

很精妙的题。

第一问，一个比较优的想法是把它和它的兄弟与父亲一起做一个轮换，这样的代价是二倍的儿子个数。

如果发现这个点已经被轮换过了，我们就不让它去参加它父亲的轮换，但这样可能有一定问题，会出现一个点的所有儿子都不能参加轮换，这时候这个点我们可以给他上传，让它参加它父亲的轮换。

这样问题又来了，根节点不能够参与轮换，因为它没有父亲了，我们特判一下这种情况就可以，随便找一个儿子和它交换一定是合法的。

第二问，这道题最精妙的一个想法就是把贡献拆到边上，一条边被贡献的最多次数是它连接的两棵子树大小取最小值，因为它做贡献肯定是从一棵子树到另一棵的形式，每一棵子树不管作为起点还是终点都只有 1 的贡献。

考虑怎么样才能把贡献堆满，直接让较小子树内的所有点必须换成一个不在这个子树的点就可以了。

我们接下来有一个思路，那就是找到重心为根，之后把每个点的 dfs 序求出，把它换到 dfs 序与其差为 \frac{n}{2} 的地方就好了。

因为重心的性质，与它交换的那个点一定出了它的所有亲辈的子树，我们把每条边都卡满了，肯定是最大值。