题解：P4764 [CERC2014] Pork barrel Luciylove · 2024-09-28 11:50:53 · 题解 最小生成树自然可以联想到 LCT。 考虑左端点扫描线维护最小生成树求出一条边什么时候有效。 注意到一条边 e 有效的时候为 R_i \geq e, L_i \in [pre_i + 1, e] 这提示我们在线二维数点，我们将贡献转为差分的形式即可。 使用主席树即可做到在线，复杂度线性对数。