P7889 「MCOI-06」Eert Tuc Knil 题解

MuYC · 2021-10-06 17:49:46 · 题解

Solution

线段树合并 + 线段树二分。

设 f_u 表示所有完全在 u 子树内并包含 u 的连通点集，权值之和最大的是多少。

那么有 f_u = \displaystyle \sum_{v \ is \ u's \ son} f_v [f_v \ge 0]。

考虑从小到大枚举 x 的过程中，一定存在一个最小的 x 使得 f_{u} \ge 0，我们设对于 u 这个最小的 x 为 t_u。

很显然，对于一个叶子节点来说，t_u = -val_u，任意一个 t_u 均可以通过二分得到，不妨假设我们现在二分到的值是 k。

注意这样一个事实：

当 v 是 u 的子树中的节点的时候，必然已经求得了 t_v。那么设 u 到 v 的路径上的所有点对应的 t 的最大值为 t_{max} 的话：

那么当 k \ge t_{max} 的时候，这个 v 就会对于 u 造成贡献，这个贡献的值就会是 k + val 。

于是可以想到开一棵线段树，以 t_u 为下标，节点 [l,r] 里面存 \sum val 以及 cnt ，其中 \sum val 表示 t 落在区间 [l,r] 中的点的和，cnt 即为有多少个节点。

但是我们这里对于每一个节点 v 不能以 t_{v} 为下标，而是要以上文的 t_{max} 为下标，于是要动态维护下标，在线段树合并之前，我们把每个以 u' 为根点的线段树中所有 t < t_{u'} 的点都移动到 t_{u'} 的位置，我们需要知道 t 在 (-10^8, t_{u'}) 的节点的个数以及它们的 \sum val 即可，这个可以直接用线段树查，修改就是单点修改。

考虑样例的那棵树：

我们假设要求 t_2，那么我们现在知道：t_{4} = -1,t_{5} = t_{7} = t_{8} = t_9 = 1（7,8,9 号点都被 5 给覆盖了）。

那么假设二分到 k = 1 的时候，那么就会是 Sum = 1 \times 5 + 1 + 1 + 1 - 5 + 1 = 4，显然大于 -val[2]，这个时候说明 k = 1 是可以的。

当 k = 0 的时候，Sum = 0 \times 1 + 1 = 1，也大于 -val[2]，可行。