题意
题目链接
分析
- 先对原树树剖，在一次删点操作后从根节点开始二分，如果一条边从重边变成轻边，必然有 \(size_u\le \frac{1}{2}size_{rt}\) (取等号是特判对应儿子消失)，二分后，将这个位置作为顶端递归寻找。容易发现这样操作的次数 \(< logn\) 次。
- 判定一条边是否从重边变成轻边的依据是父亲的重儿子之前指向 \(u\) ，同时删除节点后有 \(size_u +1 =size_{another\_son}\)，注意特判 \(u\) 是父亲子树最后一个节点的情况。
- 时间复杂度 \(O(nlog^2n)\)
代码
代码链接