noip2018-提高组 赛道修建

思路是二分答案，看当前最小最大长度能不能构成m条道路

//2018-noip 道路修复 用到树 二分 
#include<bits/stdc++.h> 
using namespace std;
const int N=50004;
inline int read(){
	char ch=getchar();
	int res=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
	return res*f;
}
int n,m,adj[N],l,r,nxt[N<<1],to[N<<1],val[N<<1],cnt,dis[N];
inline void addedge(int u,int v,int w){
	nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w;
}
multiset <int> s[N];
multiset <int>::iterator it,it1;
int fpl;
int shx;
int dfs(const int &u,const int &fa){
	s[u].clear();
	for( int e=adj[u];e;e=nxt[e]){
		int v=to[e];
		if(v==fa)
		  continue;
		int bac=dfs(v,u)+val[e];
		//cout<<"bac="<<bac<<endl;
		if(bac>=shx){
		  //u到v长度大于mid的符合条件，赛道+1 
		  ++fpl;
		  cout<<"bac="<<bac;
		  //cout<<">mid="<<shx<<" u="<<u<<" bac="<<bac<<endl;
		}
		else{
			 //cout<<"<mid="<<shx<<" u="<<u<<" bac="<<bac<<endl;
			 //比mid小的，加入multiset 
			 s[u].insert(bac);//u出发到v的路径长度 
		}
		 
	}
	int maxn=0;
	//判断s[u]是否为空
	//cout<<"mid="<<shx<<" u:"<<u<<" s[u]:";
	/*for(it1=s[u].begin();it1!=s[u].end();it1++){
		cout<<*it1<<" ";
	} 
	cout<<endl;
	*/
    while(!s[u].empty()){
    	//求最大长度 
        if(s[u].size()==1){
          return max(maxn,*s[u].begin());
        }
        //从s[u]中找到第一个>=mid-s[u].begin的数，向上传递长度 
        it=s[u].lower_bound(shx-*s[u].begin());
        //这个数在开头 
        if(it==s[u].begin()&&s[u].count(*it)==1) it++;
        //如果没找到，就用第一个长度向上传递 
        if(it==s[u].end()){
            maxn=max(maxn,*s[u].begin());
            s[u].erase(s[u].find(*s[u].begin()));
        }
		//找到了比mid-s.begin大的，说明可以向上传递构成一条赛道 
        else {
            fpl++;
            s[u].erase(s[u].find(*it));
            s[u].erase(s[u].find(*s[u].begin()));
        }
    }
    //cout<<"fpl:"<<fpl<<endl;
    return maxn;
}
//检查最小路径长度mid是否能构成m条道路 
inline bool checker(const int &k){
	shx=k;
	fpl=0;
	dfs(1,0);
	cout<<" shx="<<shx<<" fpl="<<fpl<<endl; 
	return fpl>=m;  
}
inline void solve(){
	int ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		//最小的赛道长度的最大值 
		//fpl=m 可以恰好建成m条赛道,ans=mid
		//fpl>m 可以建成多于m条赛道,mid取值偏小了，则可以扩大mid,看还能不能建成m条赛道 
		if(checker(mid))l=mid+1,ans=mid; //扩大mid 
		else r=mid-1;//mid无法建成m条赛道，则需要缩小mid再尝试 
	}
	cout<<ans;
}
//dfs
void suo(int u,int fa){
	for(int e=adj[u];e;e=nxt[e]){
		int v=to[e];
		if(v==fa)
		continue;
		dis[v]=dis[u]+val[e]; 
		suo(v,u);
	}
}
/**
7 1
1 2 10
1 3 5
2 4 9
2 5 8
3 6 6
3 7 7
**/ 
int main(){
	//读入n,m 
	n=read(),m=read();
	//读入u,v,w  二分左右端点l,r    r为所有权值之和/树的直径 
	for(int i=1;i<n;++i){
		int u=read(),v=read(),w=read();r+=w;
		addedge(u,v,w),addedge(v,u,w);
	}
	//搜索，求每条路径长度 
	suo(1,0);
	int dw=0,de=0;
	//求最大和次大，用于求直径 
	for(int i=1;i<=n;i++){
		if(dis[i]>dw)de=dw,dw=dis[i];
		if(dis[i]<dw&&dis[i]>de)de=dis[i];
	}
	r=de+dw;  //求直径,确定右端点 
	//cout<<"right="<<de<<" "<<dw<<endl;
	//树上二分 
	
	solve();
	return 0;
}