树链剖分练习题。 * CCC 肯定优先取那些 www 最大的点。 显然。 所以 CCC 应尽量取最上面的点，则我们不需要考虑 CCC 的连通性。 * 一定有最优解使 min⁡x∈Cwx≥∣C∣≥max⁡x∉Cwx\min\limits_{x \in C}w_x \ge |C| \ge \max\limits_{x \notin C}w_xx∈Cmin wx ≥∣C∣≥x∈/Cmax wx 。 因为当 ∣C∣|C|∣C∣ 增加时，max⁡x∉Cwx\max\limits_{x \notin C}w_xx∈/Cmax wx 是在不断减小的。当 ∣C∣<max⁡x∉Cwx|C| < \max\limits_{x \notin C}w_x∣C∣<x∈/Cmax wx 时，此时增加 ∣C∣|C|∣C∣ 一定不会使答案变劣。 所以我们一直增加 ∣C∣|C|∣C∣ 直至满足上述条件即停止，此时的答案 ∣C∣|C|∣C∣ 一定是最优解，且此时一定有 min⁡x∈Cwx≥∣C∣\min\limits_{x \in C}w_x \ge |C|x∈Cmin wx ≥∣C∣。†^†† * 带修怎么做？ 加入一个点时，它到根节点的路径上所有 ∈S\in S∈S 的点的 www 都会增加 111，可能会使 min⁡x∈Cwx<max⁡x∉Cwx\min\limits_{x \in C}w_x < \max\limits_{x \notin C}w_xx∈Cmin wx <x∈/Cmax wx ，此时应把 CCC 中 www 最小的点替换成 CCC 以外 www 最大的点。 此外，它可能使 max⁡x∉Cwx\max\limits_{x \notin C}w_xx∈/Cmax wx 增加，此时可能需要把它加入 CCC 中，答案增加 111。（为什么可以直接加？因为它的祖先的 www 肯定大于它本身的 www，所以祖先肯定都已经在 CCC 中了） 删除点同理，它可能使 max⁡x∉Cwx\max\limits_{x \notin C}w_xx∈/Cmax wx 减少，此时可能可以丢掉 CCC 中 www 最小的点使答案减 111。 * 维护什么？ 维护 min⁡x∈Cwx\min\limits_{x \in C}w_xx∈Cmin wx ，max⁡x∉Cwx\max\limits_{x \notin C}w_xx∈/Cmax wx 和它们的编号，以及 CCC 相关的东西。 * how？ 树链剖分+线段树维护树上路径修改，线段树维护在 CCC 中 www 的最小值和为区间中在 SSS 且不在 CCC 中 www 的最大值即可，细节见代码。 复杂度 O(qlog⁡2n)\mathcal O(q\log^2n)O(qlog2n) 虽然有点劣，但是能过。 * 代码 轻微压行，请见谅/kk ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ †^††：有人问我为什么，我解释一下。 设 aaa 为最大的满足 ∣C∣<max⁡x∉Cwx|C| < \max\limits_{x \notin C}w_x∣C∣<x∈/Cmax wx 的 ∣C∣|C|∣C∣，xxx 为此时的 min⁡x∈Cwx\min\limits_{x \in C}w_xx∈Cmin wx ，yyy 为此时的 max⁡x∉Cwx\max\limits_{x \notin C}w_xx∈/Cmax wx ，则 a<y≤xa < y \le xa<y≤x 且 a+1a+1a+1 为最优解。 再往 CCC 添加一个点后，新的 x′x'x′ 就变为了原来的 yyy，而 y>ay>ay>a，则 x′=y≥a′=a+1x' = y \ge a' = a + 1x′=y≥a′=a+1，即最优解时一定有 min⁡x∈Cwx≥∣C∣\min\limits_{x \in C}w_x \ge |C|x∈Cmin wx ≥∣C∣。