CF2152H2 Victorious Coloring (Hard Version)

MiniLong · 2025-10-08 16:47:46 · 题解

原题

先考虑已知 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 的一个函数。

• 对于叶子节点，ans_u 为一段 0 后加上一条斜率为 1 的直线，显然是凸的。

• 对于非叶子节点，ans_u 可以表示为两个凸函数之和和一个凸函数取 max，还是凸的。

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

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