题解
可以发现对于一个子树,假设移出的点为 \(u\) ,移入的点到 \(v\) ,那么这棵子树的根一定是 \(LCA(u,v)\) .于是可以设 \(dp_{u,v}\) 表示在以 \(LCA(u,v)\) 为根的子树中,移出的点为 \(u\) ,移入的点到 \(v\) ,且不算移入点的代价的最小代价.
设 \(r\) 为 \(LCA(u,v)\) , \(son\) 为 \(r\) 的儿子.
根据 \(r\) 的儿子个数 \(deg\) 转移.
-
\(deg=0\) : \(dp_{r,r}=val_r\)
-
\(deg=1\):
- 若 \(u=r\) : \(dp_{u,v}=\min\{dp_{w,v}+val_u| LCA(w,v)=son\}\)
- 若 \(v=r\) : \(dp_{u,v}=\min\{dp_{u,w}+val_u+val_v(dep_w-dep_v)|LCA(u,w)=son\}\)
-
\(deg=2\) :
-
若 \(u=r\) :
设 \(son\) 为 \(r\) 靠近 \(v\) 一侧的儿子, \(son'\) 为 \(r\) 另一侧的儿子.
先交换 \(u\) 和它的父亲,再交换 \(u\) 和 \(son\), 最后交换 \(u\) 和 \(son'\).
设 \(son\) 子树内传上来的点为 \(w\) ,它传到 \(son'\) 子树内的 \(y\) , \(son'\) 子树内传上来的点为 \(x\).
\(dp_{u,v}=\min\{dp_{w,v}+dp_{x,y}+val_u+val_w(dep_y-dep_u)|LCA(w,v)=son,LCA(x,y)=son'\}\)
-
若 \(v=r\) :
设 \(son\) 为 \(r\) 靠近 \(u\) 一侧的儿子, \(son'\) 为 \(r\) 另一侧的儿子.
先交换 \(son'\) 和 \(v\) ,再交换 \(son\) 和 \(v\) ,最后交换 \(v\) 和它的父亲.
设 \(son'\) 子树内传上来的点为 \(w\) , 它传到 \(son\) 子树内的 \(y\) , \(r\) 从 \(v\) 移到 \(son'\) 子树的 \(x\).
\(dp_{u,v}=\min\{dp_{w,x}+dp_{u,y}+val_w(dep_y-dep_v)+val_v(dep_x-dep_v)+val_u|LCA(w,x)=son',LCA(u,y)=son\}\)
-
\(v\neq r\) :
设 \(son\) 为 \(r\) 靠近 \(u\) 一侧的儿子, \(son'\) 为 \(r\) 靠近 \(v\) 一侧的儿子.
先交换 \(son\) 和 \(r\) ,再交换 \(r\) 和它的父亲,最后交换 \(son'\) 和 \(r\).
设\(x\) 为 \(r\) 移到 \(son\) 子树的 \(x\), \(y\) 为 \(son'\) 子树传上来的点为 \(y\).
\(dp_{u,v}=\min\{dp_{u,x}+dp_{y,v}+val_r(dep_x-dep_r)+val_u|LCA(u,x)=son,LCA(y,v)=son'\}\)
-