PKU 2378 Tree Cutting

http://poj.org/problem?id=2378
ノード数nの木が与えられる。
このうちの一つのノードを切り取って、ばらけた木がそれぞれもとのノードの個数の半分以下のノード数しか持たないようにしたい。
どのノード切り取ればいいかを答えるというような問題。

考え方がBalancing Act(PKU 1655)に似ている気がする問題でした。

深さ優先探索しました。
Balancing Actが他人のコードを読んでも最初よく分からなかったので（頭が残念だからかもしれませんが）自分のコードの説明をつけようと思います。

このdfs関数はノードvから先のまだ訪れていないノードの数を返す関数です。
変数cszには、そのノードを切ったときにばらけた木のうちの最大のサイズが格納されます。
そして、retがdfsの返り値になるのですが、ここでdfsに入って来た側の木のサイズはvから探索したノードを全部のノード数から引くことで計算できます。
これでそのノードからの全方向の木の最大サイズが分かります。
そうするとO(n)で全てのノードのバラけた木の最大サイズが求められるので、間に合います。

逆に分かりにくくなってしまった感がありますね。

vector<int> G[10000];
bool vis[10000];
set<int> ans;
int n;

int dfs(int v){

  vis[v]=true;
  int ret=1;
  int csz=0;
  rep(i,SZ(G[v])){
    if(vis[G[v][i]])continue;
    int df=dfs(G[v][i]);
    csz=max(df,csz);
    ret+=df;
  }
  csz=max(n-ret,csz);

  if(csz*2<=n)ans.insert(v);
  return ret;
}

main(){
  cin>>n;
  rep(i,n-1){
    int a,b;
    cin>>a>>b;
    --a,--b;
    G[a].pb(b);
    G[b].pb(a);
  }
  dfs(0);
  if(ans.empty())cout<<"NONE"<<endl;
  else{
    FOR(siter,ans)cout<<*siter+1<<endl;
  }
}