Codeforces #199 Div2. E. Xenia and Tree

Codeforces頻出の木構造探索問題。
http://codeforces.com/contest/342/problem/E

問題

N点からなる木を成すグラフが与えられる。
初期状態では1番目の点だけ赤色に塗られており、残りは青色であり。
ここで、以下のいずれかのクエリに計M回答えよ。

• i番の点を赤く塗る
• i番の点からもっとも近い赤い点までの距離を答える

解法

点を赤く塗る際に全点の最寄赤点までの距離を再計算しても、距離を問われたときに全赤点までの距離を計算してもどちらもO(N)かかるので、全体ではO(NM)程度かかりTLEする。

そこで平方分割で解くことができる。

• 赤く塗るクエリが来たら、その番号を未処理点の集合に加える。未処理点が√N程度以下ならこれだけで終了。
  • 未処理点が√N個を越えたら各未処理赤点からBFSを行い、最寄赤点までの距離を更新する。
• 距離を答えるクエリが来たら、計算済みの最寄赤点の距離と、未処理赤点までの距離の最小値を答える。
  • 未処理赤点は高々√Nなので、1クエリO(√N)で処理できる。

なお、距離を答えるクエリについて各未処理赤点までの距離事前にDFSでO(N logN)で求めた親子関係を用いてLowest Common Ancestorを使えば高速に処理できる。

以下では、未処理点上限を√Nの代わりに100個と定数て処理している。

int N,M;
vector<int> E[100001];
int D[100001],P[12][100001],TD[100001];

void dfs(int cur,int pre) {
	int j=-1;
	TD[cur]=D[cur]=(pre==-1)?0:(D[pre]+1);
	P[0][cur]=pre;
	for(int i=0;i<E[cur].size();i++) {
		int tar=E[cur][i];
		if(tar!=pre) dfs(tar,cur);
	}
}


int len(int a,int b){
	int l=0,i,oa=a,ob=b;
	if(D[a]<D[b]) swap(a,b);
	while(D[a]>D[b]) {
		i=0;
		while(D[a]-D[b]>=(1<<(i+1)) && i<=9) i++;
		l+=1<<i;
		a=P[i][a];
	}
		
	while(a!=b) {
		for(i=10;i>0;i--) if(P[i][a]!=P[i][b]) break;
		l+=2<<i,a=P[i][a],b=P[i][b];
	}
	return l;
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,-1);
	FOR(j,10) FOR(i,N) P[j+1][i]=(P[j][i]==-1)?-1:P[j][P[j][i]];
	
	set<int> NR;
	
	FOR(i,M) {
		cin>>x>>y;
		if(x==1) {
			TD[y-1]=0;
			NR.insert(y-1);
				
			if(NR.size()>100) {
				queue<int> Q;
				ITR(it,NR) Q.push(*it);
				NR.clear();
				while(!Q.empty()) {
					k=Q.front();
					Q.pop();
					FOR(j,E[k].size()) {
						int tar=E[k][j];
						if(TD[k]+1<TD[tar]) {
							TD[tar] = TD[k]+1;
							Q.push(tar);
						}
					}
				}
			}
		}
		else {
			int x=TD[y-1];
			if(x!=0) ITR(it,NR) x=min(x,len(y-1,*it));
			_P("%d\n",x);
		}
	}
	
}

まとめ

Codeforcesはほんと平方分割多いな。
もっと慣れないと…。