题意：n各节点其中1号是司令节点，叶子节点是收集信息的节点.现在破坏一些编使这个信息结构瘫痪（就是 让叶子节点和1号节点不连通）；
要求他切割的边的最大值最小，且和不能超过M
解法：很普通的的二分答案，用树形DP判断这个解是否可行。
子啊 回溯合并的时候
如果这个边的cost>枚举的答案 肯定dp 值加等 儿子节点 的dp值
否则i加等 MIN（ 儿子节点的dp值，cost）；
#include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <cstdlib> using namespace std; int n,m; const int maxn=1003; const int INF=1e6+7; struct Edge { int to,dis,pre; Edge(int to=0,int dis=0,int pre=0):to(to),dis(dis),pre(pre){} }; Edge edge[maxn*2]; int head[maxn],pos; int dp[maxn]; void add_edge(int s,int to,int dis) { edge[pos]=Edge(to,dis,head[s]); head[s]=pos++; } void inint() { memset(head,-1,sizeof(head)); pos=0; } bool jude() { return dp[1]<=m; } void dfs(int pa,int s,int mid) { dp[s]=0; for(int w=head[s];~w;w=edge[w].pre) { Edge &tmp=edge[w]; if(tmp.to==pa)continue; dfs(s,tmp.to,mid); if(tmp.dis<=mid)dp[s]+=min(dp[tmp.to],tmp.dis); else dp[s]+=dp[tmp.to]; } if(dp[s]==0)dp[s]=INF; } int main() { int a,b,c; while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0)break; inint(); for(int i=2;i<=n;i++) { scanf("%d%d%d",&a,&b,&c); add_edge(b,a,c); add_edge(a,b,c); } int l,r; l=0,r=1000000; while(l<r) { int mid=l+(r-l)/2; dfs(-1,1,mid); if(jude())r=mid; else l=mid+1; } if(l>m)printf("-1 "); else printf("%d ",l); } return 0; }