树形dp5题连做

树形dp,3天搞定

A - Information Disturbing

题意

对于一棵树,切断一些边使得每一个叶节点都无法连接到根节点,有两个要求

  • 每条边带权重,切掉的边权重和不大于$m$
  • 切掉的每条边都不能大于一个$ans$

问$ans$最小是多少?

题解

二分+树形dp


+1 ans初始化-1

看别人代码发现了个好东西,链式前项星判断节点是否为叶节点可以这样判断

1
2
3
4
if(G[head[u]].to == father) 
该节点是叶节点 //在双向边的时候适用
if(head[u]==-1)
该节点是叶节点 //在单向边的时候适用

ac代码