题解：CF2152H2 Victorious Coloring (Hard Version)

· · 题解

先看 H1

H1 告诉我们两件事情：只需要考虑染色方案是连通块；对于局部子问题最优化是正确的。

我们继续挖掘性质。先不考虑边权相等。若存在边权为 w_1 的边在连通块 内部，存在边权为 w_2 的边在连通块 边缘，那么有 w_1<w_2。

证明：若 w_1>w_2，则将连通块按照 w_1 这条边划分，选择与 w_2 这条边不交的部分，变化量 \leq -w_1+w_2< 0，所以这个染色方案一定不是最优。

所以考虑建 kruskal 最小生成树，一个可能最小的连通块是生成树的一棵子树，我们对子树内贪心。

设 a_{i} 表示 i 子树在原树上的领域边权和，f_{i,x} 表示当 L=x 时，只考虑 i 子树内染色方案的 \sum x_i 最小值。

考虑转移，对于叶子有 f_{i,L}=\max(0,L-a_i)，对于非叶子有 f_{i,L}=\max(f_{l,L}+f_{r,L},L-a_i)，其中 l,r 表示 i 的左右儿子。

然后就是一些 dirty work：发现 f_{i,*} 是凸的，证明可以归纳。考虑维护凸包的拐点和斜率 变化量（人话就是差分两次），这样可以在做 f_{l}+f_{r} 的时候比较简单合并。

对于 L-a_i 部分，这相当于凸包和直线求 \max，我们发现这条直线斜率是 1，而凸包的斜率为整数且 \geq0，所以被这个直线覆盖的点构成一段前缀，所以覆盖的时候直接暴力在前缀删点即可。

用优先队列维护凸包，启发式合并。询问时直接二分即可。时间复杂度 O(n\log^2 n+q\log n)。