JOI2009合宿 地域（Regions）

2分探索→葉っぱからできるだけ大きく切ります
分割した数+1が地域の数になります。

int n,m;
vector<vp> g;
int dived=0,maxlen;
int dfs(int v,int p){	//most distant from root
	int son=g[v].size();
	if(p!=-1) --son;
	if(son==0) return 0;
	vi dist;dist.reserve(son);
	REP(i,g[v].size()){
		pi e=g[v][i];
		if(e.sc==p) continue;
		int dep=dfs(e.sc,v);
		if(dep!=-1) dist.pb(dep+e.fr);
	}
	sort(ALL(dist));
	if(dist[0]>maxlen){
		dived+=dist.size();
		return 0;
	}else{
		int connect=0;
		REPN(i,dist.size(),1){
			if(dist[i]+dist[i-1]<=maxlen){
				connect=i;
			}else break;
		}
		dived+=dist.size()-connect-1;
		return dist[connect];
	}
}

int main(){
	FILE* fp=fopen("out.txt","w");
	scanf("%d%d",&n,&m);
	g.resize(n);
	REP(i,n-1){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b;
		g[a].pb(mp(c,b));
		g[b].pb(mp(c,a));
	}
	int lb=-1,ub=3000001;
	while(ub-lb>1){
		int md=(lb+ub)/2;
		dived=0;
		maxlen=md;
		dfs(0,-1);
		if(dived+1>m) lb=md;
		else ub=md;
	}
	fprintf(fp,"%d\n",ub);
	return 0;
}