Codeforces Round #359 (Div. 2) D. Kay and Snowflake

問題概要
ノード数nの木が与えられる。
q個のクエリが飛んでくる。
クエリの入力vに対して、ノードvのcentroidを出力せよ。

解法
自分のすべての子のcentroidが分かっているとする。
すると自分のcentroidは、自分と、最大の部分木を持つ自分の子のパス上にあることが分かる。

実装
dfs1回で書けそうな気もするが、素直に2回に分けて書いた方がよい。

#pragma comment(linker, "/STACK:256000000")

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int n, q;
vector<int> ch[300000];
int par[300000];
int maxc[300000];
int centroid[300000];
int sz[300000];

void dfs(int v) {
  sz[v] = 1;
  maxc[v] = 0;
  for (auto &w: ch[v]) {
    dfs(w);
    sz[v] += sz[w];
    maxc[v] = max(maxc[v], sz[w]);
  }
}

bool check(int v, int c) {
  return 2 * (sz[v] - sz[c]) <= sz[v] && 2 * maxc[c] <= sz[v];
}

void centroid_dfs(int v) {
  if (!ch[v].size())
    centroid[v] = v;
  else {
    int c = -1;
    for (auto &w: ch[v]) {
      centroid_dfs(w);
      if (sz[w] == maxc[v])
        c = w;
    }
    c = centroid[c];
    while (!check(v, c))
      c = par[c];
    centroid[v] = c;
  }
}

int main() {
  scanf(" %d %d", &n, &q);
  int v;
  REP (i, n-1) {
    scanf(" %d", &v);
    --v;
    par[i+1] = v;
    ch[v].push_back(i+1);
  }
  dfs(0);
  centroid_dfs(0);
  REP (i, q) {
    scanf(" %d", &v);
    printf("%d\n", centroid[--v]+1);
  }
  return 0;
}