本文出自   

 题目链接：   

 

题意

   给一棵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

 

代码