题解：P12563 [UTS 2024] Remove Node

流水行船CCD · 2025-07-31 16:49:09 · 题解

首先考虑换一种方式去思考原问题的操作（因为合并点太丑了，不好分析，考虑寻找一种不改变树形态的刻画方法）：发现其等价于每次在原树上选择一条边断开，断开的代价就是两端连通块最小值的差的绝对值，最后需要使得所有边全部断开且最小化代价和。

通过对样例的手玩，不难发现尽可能使最小值最早被删成孤立点（即删除最小点的所有出边）一定最优。证明不妨设 x 是最小点，考虑 x 的出边 (x,y)，不妨设我们先删去了 y 方向连通块的一条边 (u,v)，橙色联通块最小值为 A，绿色联通块最小值为 B，此时的代价就是 (A-a_x)+(B-a_x)，不优于先删 (x,y) 的代价 (\min(A,B)-a_x)+|A-B|。所以每次选权值最小的点，将其出边全部删除，这样得到的方案就是最优解。

可以做到 O(nq) 或 O(nq\log n)，有 17 分。

由于答案形如：\sum a_y-a_x(a_x \le a_y)，考虑分别统计 \sum a_x（作为最小点）和 \sum a_y（作为最小点出边连通块中的最小点）的值。

首先考虑 \sum a_x 的值，考虑每一条边被断开时是以哪个端点为最小点，因此其可以写成：

可以用一棵平衡树/值域线段树维护一个点所有儿子的权值集合，那么不难通过线段树二分在 O(\log n) 的时间中求得一个点到它儿子所有边的贡献和，把这个贡献和放在一颗 dfn 线段树上就可以支持单点修改，子树查询了。

平衡树优势是空间线性，动态开点值域线段树优势是常数相对较小且实现简易。

其次考虑 \sum a_y 的值，由于一个点作为某一个最小点 x 出边连通块中的最小点计算过一次后，那么下一次该出边连通块中删点时它一定就会作为最小点了，也就是说每个点至多被作为某个最小点出边连通块中最小点计算一次！考虑哪些点从来没有被计算过，发现只有最开始的最小点！

所以使用 dfn 线段树维护子树的权值和和最小值即可。