题解：CF2152H2 Victorious Coloring (Hard Version)

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)$。