1D8 ya。
设 \(f_{u,i}\) 表示覆盖了 \(u\) 子树并且向上覆盖到了深度为 \(i\) 的最小代价。
考虑合并儿子 \(v\):
\[f'_{u,i}\gets \min\left(f_{u,i}+\min\limits_{j=1}^nf_{v,j},f_{v,i}+\min\limits_{j=1}^nf_{u,j}\right) \]相当于区间加，单点取 \(\min\)，区间求最小值。
直接线段树合并维护就没了，可能要写垃圾回收。复杂度 \(O(n\log n)\)。
标签：Yusland,limits,min,CF671D,nf,Roads From： https://www.cnblogs.com/Ender32k/p/17720661.html