CF2152H2 Victorious Coloring (Hard Version)

先考虑已知 $x_i$ 怎么求 $f(x_i)$。设 $a_u$ 为 $u$ 头上的边，朴素的想法是直接 dp，$dp_u = a_u + \sum\limits_v \min(dp_v - a_v, a_v)$，然后对 $l$ 取 $\max$，但是这个做法无法优化，故舍去。

先对原图找一点性质：对于最小的连通块，不存在一条内部到外部的边 $w_i$ 比内部任意一条边的 $w_j$ 大，否则可以让内部那条 $w_j < w_i$ 的 $j$ 作为内部到外部的边。所以从大往小加边，那么就只有每次加完边的连通块和一开始的孤点可能成为 $f(x_i)$。

考虑求答案，设 $sum(S)$ 为联通块 $S$ 的内部到外部边权和，$ans_S$ 为 $S$ 内部的 $x$ 之和，显然要有 $\forall S,ans(S) \ge l - sum(S)$。

容易发现，上面的连通块可以通过 kruskal 重构树来表示，每个连通块就是一个子树，那么就有 $ans_u = \max(ans_{ls_u} + ans_{rs_u}, l - sum(u))$。

考虑直接维护 $ans_u(l)$ 为关于 $l$ 的一个函数。

用 slope trick 维护这个凸函数，合并两个子树的时候直接把两个堆 merge，取 max 的时候只用看最小的若干个点被一条斜率为 $1$ 的直线弹掉即可，每次只会加 $O(1)$ 个点。

所以复杂度为 $O(n\log^2 n+q\log n)$ 或 $O((n+q)\log n)$，取决于是否使用可并堆。