PKU 3107 Godfather
http://poj.org/problem?id=3107
n個のノードからなる木が与えられる。
この時、あるノードを消したときに、ばらされた子木のサイズの最大が最小になるようなノードを全て求めろというような問題。
久しぶりにPKU先生の本気を見た、ような気がします。
cinをscanfに変えてもダメ、入力を独自にとってもダメ。
vector
今さらながらjavaに逃げるという手も無くはなかったのかなと思ったり・・・。
PI G[100000]; int Gs[50000]; int Gss; bool vis[50000]; int ans[50000]; int as; int minnum; int n; int ret; int c; int in(){ ret=0; while(!isdigit(c=getchar())); ret=c-'0'; while(isdigit(c=getchar()) && c!=EOF)ret=(ret<<3)+(ret<<1)+c-'0'; return ret; } int dfs(int v){ vis[v]=true; int ret=1; int minc=0; for(int i=Gs[v];G[Gs[v]].F==G[i].F;i++){ int to=G[i].S; if(vis[to])continue; int cc=dfs(to); minc=max(cc,minc); ret+=cc; } minc=max(minc,n-ret); if(minc==minnum)ans[as++]=v+1; else if(minc<minnum)as=0,ans[as++]=v+1,minnum=minc; return ret; } main(){ n=in(); int a,b; rep(i,n-1){ a=in(),b=in(); --a,--b; G[Gss++]=mp(a,b); G[Gss++]=mp(b,a); } sort(G,G+Gss); rep(i,Gss-1){ if(G[i].F!=G[i+1].F)Gs[G[i].F+1]=i+1; } Gs[0]=0; minnum=n; dfs(0); sort(ans,ans+as); rep(i,as){ if(i)putchar(' '); printf("%d",ans[i]); } putchar('\n'); }