算法：hdu 3586 Information Disturbing（树形dp + 二分）

算法：hdu 3586 Information Disturbing（树形dp + 二分）2014-01-01 csdn shuangde800题意

给一棵n个节点的树，节点编号为1～n，根节点为1。每条边有权值，砍掉一条边要花费cost（w）

要砍掉一些边，使得每个叶子节点无法走到根节点。

要求砍掉花费总和不能超过m的情况下，让每条边花费上限尽量低

思路

二分可以砍的边的权值上限，然后树形dp

f[i]: 表示让i子树所有的叶子节点无法到达i点的最小花费

f[i] = sum { min（w（i,v）, f[v]） | v是i的儿子节点 }

而这题有一个上限权值，即权值大于上限的就不能去砍。

所以上面的转移要改一下

if （w（i, v） > 上限） f[i] += f[v];

else f[i] += min（w（i,v）, f[v]）;

然后，如果f[1]<=m，那么这个上限就符合条件

这一题，如果用INF初始化的话，那么INF一定要大于m的最大值1000000