[JSOI2016]轻重路径[树链剖分]

题意

题目链接

分析

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

代码

代码链接