树形dp5题连做
树形dp,3天搞定
A - Information Disturbing
题意
对于一棵树,切断一些边使得每一个叶节点都无法连接到根节点,有两个要求
- 每条边带权重,切掉的边权重和不大于$m$
- 切掉的每条边都不能大于一个$ans$
问$ans$最小是多少?
题解
二分+树形dp
+1 ans初始化-1
看别人代码发现了个好东西,链式前项星判断节点是否为叶节点可以这样判断
1 | if(G[head[u]].to == father) |
对于一棵树,切断一些边使得每一个叶节点都无法连接到根节点,有两个要求
问$ans$最小是多少?
二分+树形dp
+1 ans初始化-1
看别人代码发现了个好东西,链式前项星判断节点是否为叶节点可以这样判断
1 | if(G[head[u]].to == father) |