はまやんはまやんはまやん

hamayanhamayan's blog

Kay and Snowflake [Codeforces 359 : Div1 B, Div2 D]

問題

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);
	}
}