PKU 3107 Godfather

http://poj.org/problem?id=3107
n個のノードからなる木が与えられる。
この時、あるノードを消したときに、ばらされた子木のサイズの最大が最小になるようなノードを全て求めろというような問題。

久しぶりにPKU先生の本気を見た、ような気がします。
cinをscanfに変えてもダメ、入力を独自にとってもダメ。
vectorを使うとTLEを防ぐ方法が分からず、隣接行列でもつと当然のようにMLEするので、とても変な形でグラフを持つことになりました。

今さらながら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');
}