World CodeSprint 13 : G. Dynamic Trees

その解法は思い浮かばなかった。
https://www.hackerrank.com/contests/world-codesprint-13/challenges/dynamic-trees

問題

1～Nの頂点が振られたN頂点の根付き木を成すグラフが与えられる。
このグラフは1番の頂点を根とし、辺の両端の頂点は常に根側が小さい番号を持つ。
各頂点は白黒いずれかの色で塗られている。
以下のクエリに順次答えよ。

• 指定された番号の頂点の色を反転する
• 頂点uと親頂点の辺を消し、uの親がvとなるようつなぎなおす。
• 頂点対(u,v)と整数kが与えられる。u→vに向かう最短経路において、k番目に登場する黒頂点の番号を答えよ。

解法

木のつなぎ替えなのでLinkCut-Treeが頭をよぎるが、平方分割でも解ける。
D=√Nの単位で頂点をグループ化しよう。
頂点を先頭から番号順にD個ずつグループ化する。
各グループ内では、頂点は森を成す。

各グループにおいて、各頂点vに対し以下の値を計算しよう。

• 親頂点を順次辿って行った場合、グループ内の範囲でたどり着く最も根に近い頂点番号
• 上記頂点にたどり着くまでに経由する黒頂点数

先頭２種類のクエリに対しては、対象頂点のグループだけ状態を更新すればよく、O(D)で処理できる。
このような情報を持っておくと、各頂点から初めて次のグループに至るまでの黒頂点数とその頂点番号がわかるので、３番目のクエリにおいてuとvのLCAに至るまでの黒頂点数がO(N/D)で求められる。

よってD=O(√N)にしておくと、クエリ数Qに対し全体がO(Q√N)で済む。

int N,Q,K;
int P[101010];
int C[101010];
int S[101010];
int BP[101010];
const int DI=330;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>C[i];
	for(i=1;i<N;i++) cin>>P[i], P[i]--;
	
	FOR(i,N) {
		if(i && i/DI == P[i]/DI) {
			S[i]=S[P[i]]+C[i];
			BP[i]=BP[P[i]];
		}
		else {
			S[i]=C[i];
			BP[i]=i;
		}
	}
	
	while(Q--) {
		cin>>s;
		if(s=="T" || s=="C") {
			if(s=="T") {
				cin>>x;
				x--;
				C[x]^=1;
			}
			else {
				cin>>x>>y;
				x--,y--;
				P[x]=y;
			}
			for(i=x/DI*DI;i<min(N,(x/DI+1)*DI);i++) {
				if(i && i/DI == P[i]/DI) {
					S[i]=S[P[i]]+C[i];
					BP[i]=BP[P[i]];
				}
				else {
					S[i]=C[i];
					BP[i]=i;
				}
			}
		}
		else {
			cin>>x>>y>>K;
			x--,y--;
			int tx=x,ty=y,sx=0,sy=0,num=0;
			while(BP[tx]!=BP[ty]) {
				if(tx>ty) sx+=S[tx], tx=P[BP[tx]];
				else sy+=S[ty], ty=P[BP[ty]];
			}
			while(tx!=ty) {
				if(tx>ty) sx+=C[tx],tx=P[tx];
				else sy+=C[ty],ty=P[ty];
			}
			sy+=C[ty];
			
			if(sx+sy<K) {
				cout<<-1<<endl;
			}
			else if(K<=sx) {
				hogege:
				while(K>S[x]) {
					K-=S[x];
					x=P[BP[x]];
				}
				while(K) {
					K-=C[x];
					if(K==0) break;
					x=P[x];
				}
				cout<<x+1<<endl;
			}
			else {
				K=sy+1-(K-sx);
				x=y;
				goto hogege;
			}
			
			
		}
	}
	
	
}

まとめ

LC Tree、一度実装してみようかな。