問題
http://codeforces.com/contest/686/problem/D
n頂点の木が与えられる。
クエリとしてk個の頂点が与えられるので、その頂点からの部分木のcentroidを求めよ
centroidとは、その木の中でそのノードを消すと、各連結成分の要素数が元の木の要素数の半分以下になるノードのこと
2 <= n <= 3*10^5
1 <= q <= 3*10^5
思考の流れ
1. クエリ数が10^5で各クエリ毎に出力する必要があるため、各クエリをO(1)かO(logn)で計算する必要がある
2. クエリの処理によって答えが変わるようなものでもない -> 事前処理して置くことでO(1)で処理できるようにする
ここで、どのようなノードがcentroidになるか考えてみる
3. ある木の要素数がn要素であれば、1つ消すので、残るn-1要素の半分、(n-1)/2要素の連結成分が作れれば良い
4. （若干飛躍ですが）ある木の子ノードの中で、そこからの部分木が(n-1)/2要素を初めて越えるノードがcentroid
なので、とりあえず、木の子ノードの数を数える -> DFSで簡単にできる
5. あるノードからcentroidを探すには子ノードの数が多い子ノードを辿っていけば良い(HL分解)
6. そのままやると計算量がやばそうなので、子ノードの数が多い子ノードから根に向かって走査し、小ノードの数が初めてあるノードの小ノード数の半分を超えたら、それがcentroidである
解法
int n, q; vector<int> E[301010]; int par[301010]; //----------------------------------------------------------------- int num[301010]; int maxc[301010]; void dfs1(int i) { num[i] = 1; maxc[i] = 0; for (int j : E[i]) if (par[i] != j) { dfs1(j); num[i] += num[j]; maxc[i] = max(maxc[i], num[j]); } } //----------------------------------------------------------------- int ans[301010]; void dfs2(int i) { if (num[i] == 1) { ans[i] = i; return; } int c; for (int j : E[i]) if(par[i] != j) { dfs2(j); if (num[j] == maxc[i]) c = j; } c = ans[c]; while (num[c] * 2 < num[i]) c = par[c]; ans[i] = c; } //----------------------------------------------------------------- int main() { scanf("%d %d", &n, &q); par[0] = -1; rep(i, 1, n) { int p; scanf("%d", &p); p--; E[i].push_back(p); E[p].push_back(i); par[i] = p; } dfs1(0); rep(i, 0, n) ans[i] = -1; dfs2(0); rep(i, 0, q) { int v; scanf("%d", &v); v--; printf("%d\n", ans[v] + 1); } }
