记录编号	600830	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2018]赛道修建	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	1.858 s
提交时间	2025-05-19 18:56:18	内存使用	28.19 MiB

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
const int INF=0x3f3f3f3f;
int a,b,p,res,x,y,z,mx,l=1,r,ans,s[N],nxt[N],lst[N],Fa[N];
bool vis[N];
vector<pair<int,int> >st[N];
int f(int n){
	return Fa[n]==n?n:Fa[n]=f(Fa[n]);
}
void dfs(int n,int fa){
	s[n]=0;
	vector<int> q;
	q.clear();
	for(int i=0;i<st[n].size();i++){
		int v=st[n][i].first,val=st[n][i].second;
		if(v==fa){
            continue;
        }
		dfs(v,n);
		if(s[v]+val>=p){
            res++;
        }else{
            q.push_back(val+s[v]);
        }
	}
	if(!q.size()){
        return;
    }
	if(q.size()==1){
		s[n]=q[0];
		return;
	}
	sort(q.begin(),q.end());
	for(int i=0;i<=(int)q.size();i++){
        Fa[i]=i;
        vis[i]=0;
    }
	for(int i=0;i<(int)(q.size()-1);i++){
		if(vis[i]){
            continue;
        }
		if(i>=q.size()-1||i==-1){
            break;
        }
		int t=lower_bound(q.begin()+i+1,q.end(),p-q[i])-q.begin();
		if(t>=q.size()){
            continue;
        }
		t=f(t);
		if(t>=q.size()){
            continue;
        }
		if(q[t]+q[i]<p){
            continue;
        }
		vis[t]=1;
		vis[i]=1;
		Fa[t]=t+1;
		res++;
	}
	for(int i=(int)(q.size()-1);i>=0;i--){
        if(!vis[i]){
            s[n]=q[i];
            break;
        }
    }
}
bool check(int n){
	p=n;
	res=0;
	dfs(1,0);
	return res>=b;
}
signed main(){
			freopen("2018track.in","r",stdin);
				freopen("2018track.out","w",stdout);
	cin>>a>>b;
	for(int i=1;i<a;i++){
		cin>>x>>y>>z;
		mx+=z;
		st[x].push_back(make_pair(y,z));
		st[y].push_back(make_pair(x,z));
	}
	r=mx;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)){
            l=mid+1;
            ans=mid;
        }else{
            r=mid-1;
        }
	}
	cout<<ans<<endl;
	return 0;
}