题解：P14157 [ICPC 2022 Nanjing R] 树的染色

FstAutoMaton · 2025-10-10 16:24:06 · 题解

[ICPC 2022 Nanjing R] 树的染色

先考虑 dp。设 f_{i,j} 表示 i 子树内深度为 j 的点全部被染成黑色的最小代价，转移时将所有儿子的 f 的第 j 个位置加上，然后再对直接操作的代价取 min 即可。

这样时间复杂度是 \operatorname{O}(n^2) 的，用长链剖分可以将第一部分做到 \operatorname{O}(n)，但第二部分难以优化。

观察到不同深度实际上没必要一起计算，可以分开计算。设当前考虑的深度为 x，那么对子树操作时如果只有一个儿子的子树中存在深度为 x 的点其能一次操作变黑的点是一样的，这启发我们只保留那些有至少两个儿子的子树中存在黑点的点，也就是对深度为 x 的点建虚树。

考虑虚树上两点 x 和 y，设 x 为 y 祖先，v 为 x 向 y 走到的第一个点，那么 y 到 v 路径上的点在操作时影响的点都是一样的，而这些点的 a 对应的是一段连续的区间，用 ST 表快速维护即可。