题解：P14157 [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 表快速维护即可。