JOI 2010 春合宿 day2-3「Regions」

２分探索。
調べるときは葉からしなければならない。

#include<cstdio>
#include<vector>
#include<queue>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int> P;

vector<P> e[300001], d[300001];
int z[300001], divm, mid;


int f(int i){
	int nd, d1;
	priority_queue<int> qd;
	qd.push(0); qd.push(0);
	rep(j,d[i].size()){
		nd = f(d[i][j].fi) + d[i][j].se;
		qd.push(nd);
	}
	
	d1 = qd.top(); qd.pop();
	while(d1 + qd.top() > mid){
		d1 = qd.top(); qd.pop();
		divm ++;
	}
	
	return d1;
}


int main(){
	int n, m, a, b, c, x, l = 0, r = 3000000;
	P p;
	queue<int> q;
	
	scanf("%d%d",&n,&m);
	
	rep(i,n-1){
		scanf("%d%d%d",&a,&b,&c);
		e[a].pb(P(b,c));
		e[b].pb(P(a,c));
		z[a]++; z[b]++;
	}
	rrep(i,n) if(z[i] == 1) q.push(i);
	
	while(!q.empty()){
		x = q.front(); q.pop();
		z[x] = -1;
		rep(i,e[x].size()){
			p = e[x][i];
			z[p.fi]--;
			if(z[p.fi] == 1) q.push(p.fi);
			if(z[p.fi] < 0) d[x].pb(P(p.fi, p.se));
		}
	}
	
	
	while(l < r){
		mid = (l+r) / 2; divm = 1;
		f(x);
		if(divm > m) l = mid+1; else r = mid;
	}
	
	
	printf("%d\n",l);
	
	return 0;
}