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; }