P2700 逐个击破——贪心/树上dp

· · 个人记录

观察

注意到需要把树划分成k个连通块，要断k-1条边

但是并查集要分离集合有点难，都搅在一起了

平衡树感觉太扯了

然后到这里就什么都想不出来了……

正难则反

最小代价 = 总代价 - 最大节省

那么最大节省是什么呢？就是留的那些边

于是变成了最大生成森林

Kruskal模板

树形dp

就要写dp😡

第二维出现的原因是转移时需不需要断不断边取决于敌人在不在 $u$ 所在连通块 #### 状态转移 - $u$ 有敌人时： - $$dp_{u,0}=+\infty$$ - $$dp_{u,1}=\sum_{v \in son_u}\min(dp_{v,0},dp_{v,1}+w_{u,v})$$ - $u$ 没有敌人时： - $$dp_{u,0}=\sum_{v \in son_u}\min(dp_{v,0},dp_{v,1}+w_{u,v})$$ - $$dp_{u,1}=dp_{u,0}-\min_{v \in son_u}\big(\min(dp_{v,0},dp_{v,1}+w)+\min(dp_{v,0},dp_{v,1})\big)$$ (可以有一条边不断)