题解：CF2231E Graph Cutting

Wei_Han · 2026-05-22 11:32:45 · 题解

来点没有脑子做法。

枚举两个点 u,v，考虑第三个点的位置，记当前剩余需要的大小为 d。

显然 \operatorname{lca} 子树外距离 \operatorname{lca} 为 d 的点都是答案，子树内分为 u 到 \operatorname{lca}，v 到 \operatorname{lca}，这两条路径都取不到 \operatorname{lca}，和 \operatorname{lca} 自己的这三部分。前两部分可以预处理每个点子树内轻儿子距离为 d 的数量，做个前缀和就可以链查询了，然后每次暴力修改一下链头，复杂度 O(\log n)。\operatorname{lca} 自己只需要把 u,v 两个子树扣掉求别的子树距离为 d 的就行了。

这三个点会被算重 6 次，除掉就行了。

以上所有预处理都可以在 O(n^2) 时间内完成，复杂度 O(n^2\log n)。

\text{Submission}