AOJ 2170: Marked Ancestor

解法

想定解は、後ろからUnionFindらしい。賢い。

この問題は(実装が重くなるが)平方分割でも解けて、
MクエリがB回来るたびにO(N)で全部の頂点を更新すると、Qクエリをダブリングを用いてO(BlogN)で処理でき、全体でO(Q*(N+BlogN))となるので B = √(NlogN)程度にすると効率的に解くことができる。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
#define N 100000
#define M 20
#define R 300
int p[N][M], c[N], d[N], e[N];
vector<vector<int> > g;

int main(){
	int n, Q;
	while(scanf("%d%d",&n,&Q), n){
		memset(c, 0, sizeof(c));
		memset(p, 0, sizeof(p));
		g = vector<vector<int> >(n);
		for(int i = 1; i < n; i++){
			int a;
			scanf("%d",&a);
			a--;
			p[i][0] = a;
			g[a].push_back(i);
		}
		for(int i = 1; i < M; i++)
			for(int j = 0; j < n; j++)
				p[j][i] = p[p[j][i-1]][i-1];
		d[0] = 0;
		queue<int> q;
		q.push(0);
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(int i = 0; i < g[u].size(); i++){
				int v = g[u][i];
				d[v] = d[u]+1;
				q.push(v);
			}
		}
		long res = 0;
		for(int i = 0, cnt = 0; i < Q; i++){
			char qr;
			int a;
			scanf(" %c%d",&qr,&a);
			a--;
			if(qr=='M'){
				c[a] = a;
				e[cnt++] = a;
			} else {
				if(cnt>R){
					q.push(0);
					while(!q.empty()){
						int u = q.front(); q.pop();
						for(int i = 0; i < g[u].size(); i++){
							int v = g[u][i];
							if(c[v]!=v) c[v] = c[u];
							q.push(v);
						}
					}
					cnt = 0;
				}
				int r = c[a];
				for(int j = 0; j < cnt; j++){
					int t = e[j], dd = d[t];
					if(dd<=d[r] || d[a]<dd) continue;
					int s = d[a]-dd, b = a;
					for(int k = 0; s>>k; k++)
						if(1&(s>>k)) b = p[b][k];
					if(b==t) r = t;
				}
				res += r+1;
			}
		}
		printf("%ld\n", res);
	}

	return 0;
}