传送门
换根dp入门题。
貌似李煜东的书上讲过？
不记得了。
先推出以1为根时的答案。
然后考虑向儿子转移。
我们记f[p]f[p]f[p]表示原树中以ppp为根的子树的答案。
g[p]g[p]g[p]表示把根换成ppp时整棵树的答案。
于是有g[v]=f[v]+min(g[p]−min(e[i].c,f[v]),e[i].c)g[v]=f[v]+min(g[p]-min(e[i].c,f[v]),e[i].c)g[v]=f[v]+min(g[p]−min(e[i].c,f[v]),e[i].c)
注意边界之后就能过了。
代码