搭建邮箱网站链接地址

给定一棵由 N个节点构成的带边权树。节点编号从 0到 N−1，其中 0 号点为根节点。最初，从根节点可以抵达所有节点（包括自己）。如果我们将所有边权小于 X 的边全部删掉，那么从根节点可以抵达的节点数目就可能发生改变。
现在，给定一个整数 Y，请你找到最小的非负整数 X，使得所有边权小于 X
的边都被删掉以后，根节点能够抵达的节点数目（包括自己）不超过 Y。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。每组数据第一行包含两个整数 N,Y。
接下来 N−1行，每行包含三个整数 U,V,W，表示点 U 和点 V 之间存在一条权值为 W 的边。

输出格式
每组数据输出一行，一个 X。
注意，X 应不小于 0。

数据范围
1≤T≤100,
1≤N≤20000,
1≤Y≤N,
0≤U,V<N,
0≤W≤107,

保证在一个测试点中，所有 N 的和不超过 105。

输入样例：
2
3 2
0 1 2
0 2 3

6 3
0 1 8
0 2 3
1 3 2
1 4 5
2 5 6

输出样例：
3
4

#include<iostream>
#include<cstring>
using namespace std;
const int N=20010,M=N*2;
int h[N],e[M],ne[M],w[M],idx; //头结点、邻接表结点、指针、权、插入的第几个结点。
void add(int a,int b,int c)
{e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dfs(int u,int mid,int fa) //从第u个节点遍历，mid为答案，fa为父节点
{int res=1; //从父节点开始可以遍历到的节点for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa||w[i]<mid) continue;//如果次节点边权小于答案，说明该节点被删除后无法到达根节点。res+=dfs(j,mid,u);}return res;
}
int main()
{int T;cin>>T;while(T--){int n,y;cin>>n>>y;idx=0; //每次输出将邻接表清空memset(h,-1,sizeof(h));for(int i=0;i<n-1;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);  //树为特殊的无向图add(b,a,c);}int l=0,r=1e8;while(l<r){int mid=(l+r)/2;if(dfs(0,mid,-1)<=y) r=mid; //当答案小于y时说明答案在y左边，r=mid;else l=mid+1;}cout<<r<<endl;}return 0;
}