AcWing 3712. 根能抵达的点
原题链接
简单
作者:
飞舞
,
2021-06-22 23:25:50
,
所有人可见
,
阅读 429
二分,图论
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e4+10, M = N;
int n,m;
int h[N], e[M], w[N], ne[M], idx;
void add(int a, int b, int c) // 添加一条边a->b,边权为c
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int getnum(int u,int x){
int ans=1;
for(int i=h[u];i!=-1;i=ne[i]){
if(w[i]<x) continue;
ans+=getnum(e[i],x);
}
return ans;
}
int main()
{
int T;cin>>T;
while(T--){
cin>>n>>m;
for(int i=0;i<n;i++){
h[i]=-1;
}
idx=0;
int a,b,c;
for(int i=1;i<n;i++){
cin>>a>>b>>c;
add(a, b, c);
}
int l=0,r=1e7+10;
while(l<r){
int mid=(l+r)>>1;
if(getnum(0,mid)<=m) r=mid;
else l=mid+1;
}
cout<<l<<endl;
}
return 0;
}
厉害,互赞