PKU : 3107 - Godfather

問題概要

http://poj.org/problem?id=3107

連結なツリー構造が与えられます.
この中のノードをひとつ消したとき, 複数のツリーに分割されます.
分割された各ツリーのノード数の最大が最小化されるようにするためには, どのノードを消せばいいでしょうか.

アルゴリズム

DFSで解けます.
DFSをしながら最小値を更新していきましょう.

この問題では, DFSが想定解法だと思われますが, PKUでは何かしら工夫しないと通らないようになっているようです.
C++でやる人はがんばってください(limitは2秒)
僕は, C++でTLEとか言われたので, Javaに逃げました(limitは10秒)

プログラム

static int n,ansMin;
static ArrayList<ArrayList<Integer>> map;
static ArrayList<Integer> ans;
static boolean[] used;

static int dfs(int id){
  int res = 1;
  int maxCnt = 0;
  used[id] = true;

  for(int next : map.get(id)){
    if(!used[next]){
      int cnt = dfs(next);
      res += cnt;
      if(maxCnt < cnt) maxCnt = cnt;
    }
  }

  if(maxCnt < n-res) maxCnt = n - res;

  if(maxCnt == ansMin){
    ans.add(id+1);
  }
  else if(maxCnt < ansMin){
    ansMin = maxCnt;
    ans = new ArrayList<Integer>();
    ans.add(id+1);
  }

  return res;
}

public static void main(String[] args)throws IOException{
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  while(br.ready()){
    n = Integer.parseInt(br.readLine());
    map = new ArrayList<ArrayList<Integer>>();
    for(int i=0;i<n;i++){
      map.add(new ArrayList<Integer>());
    }
    for(int i=1;i<n;i++){
      String[] s = br.readLine().split(" ");
      int a = Integer.parseInt(s[0]) - 1;
      int b = Integer.parseInt(s[1]) - 1;
      map.get(a).add(b);
      map.get(b).add(a);
    }

    used = new boolean[n];
    ansMin = Integer.MAX_VALUE;
    dfs(0);

    Collections.sort(ans);
    System.out.println(ans.toString().replaceAll("\\[|\\]|,",""));
  }
}