CF1827D 题解

problem & blog。

很好的题。用到一些关于重心的 trick。

不妨认为只有一个重心 \(\text{maxx}\)。设当前节点数为 \(n\)，重儿子所在的子树的大小为 \(\text{maxsiz}\)，那么答案即 \(n - 2\times\text{maxsiz}\)，方法是往重儿子的那个子树爆加节点。

因此需要在线维护 \(\text{maxx}\) 与 \(\text{maxsiz}\)。假设已知上一次操作的 \(\text{maxx}\) 与 \(\text{maxsiz}\)，分类讨论以求出新的值。

• \(u\) 在 \(\text{maxx}\) 的子树里。若新的子树超过了 \(\left\lfloor\dfrac n2\right\rfloor\)，更新 \(\text{maxx}=u,\text{maxsiz}=\left\lfloor\dfrac n2\right\rfloor\)。否则，直接更新 \(\text{maxsiz}\)。
• \(u\) 不在 \(\text{maxx}\) 的子树里。过程和上面类似，只是添加到 \(fa_u\) 对应的地方。

新的子树的 \(\text{siz}\) 用树状数组维护维护 dfs 序即可。实现方面，还要写个倍增跳 \(k\) 级祖先的操作，整体细节不多。

代码，时间复杂度 \(O(n\log n)\)。