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