摘要
神仙题
树上选若干点,选一个点的代价为 $x$
一个点到最近选中点距离(边数)为 $d$ 产生 $D_d$ 的代价
求最小代价和
题面
解
树形DP
考虑在状态里钦点一些东西
比如钦点 $i$ 的距离
很难转移,因为一个距离对应的点数情况(祖先、兄弟……)太多了
钦点 $i$ 到哪个点去
难点就在于一个选中点计入一次贡献
考虑选完之后每个选中点的统辖范围是一个联通块
在连通块最上端作贡献,即父子归属不同的位置
Code
1 |
|
神仙题
树上选若干点,选一个点的代价为 $x$
一个点到最近选中点距离(边数)为 $d$ 产生 $D_d$ 的代价
求最小代价和
树形DP
考虑在状态里钦点一些东西
比如钦点 $i$ 的距离
很难转移,因为一个距离对应的点数情况(祖先、兄弟……)太多了
钦点 $i$ 到哪个点去
难点就在于一个选中点计入一次贡献
考虑选完之后每个选中点的统辖范围是一个联通块
在连通块最上端作贡献,即父子归属不同的位置
1 | #include <cstdio> |