LOJ#6020. 「from CommonAnts」寻找 LCT

link of problem。

依旧是非常精妙的做法呢！问了神仙 lca 才知道怎么做了，目前网上是没有题解的，有的只是一份带注释的代码的英文题解。

我的细节实现也是看了这份代码得以补足的。

我们定义一些量：原树重心为 rt，rt 的某个儿子叫做 son，son 子树内的某个节点为 x。

首先考虑哪些连通块大小会 \(> \lfloor \frac n2 \rfloor\)？明显的，包含 rt 的连通块。

因此这里有一个结论，我们只会删除与 rt 相邻的边，因为原来的树重心本身就将树分为 \(\leq \lfloor \frac n2 \rfloor\) 的块了。

我们的做法是求出对于每个 x，最少所需要的 cut-link 操作，判断是否 \(\leq k\) 即可。

我们先求出 rt，预处理出以 rt 为根，每个点的 siz,dep,dfn,id(dfn to point id)。

提取出所有 son 的 siz，从大到小排序（贪心地想，我们每次删除的一定是能砍掉最多的边，顺便提及，我们在每次 cut 后，总是将其 link 到 x 上，这样最好），求其前缀和数组 sum。

接着枚举 son，对于 son 的子树内的点逐一求解。

在 sum 数组上二分，我们到底需要删除多少条与 rt 相邻的边，才能让 x 作为重心。

如果你 cut 了 son，这明显是无用的，直接将二分的值加上 siz[son]，相当于直接跳过了 son。

至此，大致思路已经完毕。

细节：还可能是先让 son 作为重心，再花 1 的代价挪到 x 来。

code。