hogloidのブログ

へなちょこ

SPOJ 2798 Query on a tree again!

http://www.spoj.pl/OI/problems/QTREE3/
問題概要
Nノードからなる重みなし・無向全域木がある。
ノードには黒・白の色がある。以下のクエリーに答えよ

  • ノードiの色を変える(最初はすべて白)
  • ノード1からノードvへのパスのうち、最もノード1に近くて、色が黒のノードの番号を答えよ なければ-1

N<=100000、クエリー数<=400000


















方針

ノード1を根にする。
centroid-path decompositionを使う
パスに分解し、あるノードがどのパスに属するか、パスの根から見て何番目かなどを記録。
色が黒になるときは、パスごとに用意したpriority_queueにそのノードをpush
(根からの距離で並ぶようなpriority_queue)
白にするときは、削除用priority_queueを用意して、値を取り出すときに削除させる(遅延処理?)
答えるクエリーには、vから根への圧縮されたパスを根の方からみて、
それぞれのパスで、最も根に近いものが根からvへのパスに入っているならそれが答え
なければ、次のパスで探す
priority_queueのtop()はO(1)で、あるノードからvまでの圧縮されたパスの数はO(logN)なので、
O(QlogN)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>

using namespace std;
static const int INF =500000000;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
int n,q;
vector<int> g[100005];
int par[100005],size[100005];
int belong[100005],rank[100005];
int par_p[100005],join[100005];
struct comp{
	bool operator ()(int a,int b)const {
		return rank[a]>rank[b];
	}
};
priority_queue<int,vector<int>,comp>pq[100005],del[100005];
int cnt,cnt2;
void prep(int v,int p){
	par[v]=p;
	size[v]=1;
	for(int i=0;i<g[v].size();++i){
		int to=g[v][i];
		if(to==p) continue;
		prep(to,v);
		size[v]+=size[to];
	}
}
void dfs(int v,int p){
	par[v]=p;
	int maxi=-1,who;
	belong[v]=cnt;
	rank[v]=cnt2++;
	for(int i=0;i<g[v].size();++i){
		int to=g[v][i];
		if(to==p) continue;
		if(maxi<size[to]){
			maxi=size[to];
			who=to;
		}
	}
	if(maxi==-1){
		++cnt;
		cnt2=0;
		return;
	}
	dfs(who,v);
	for(int i=0;i<g[v].size();++i){
		int to=g[v][i];
		if(to==p || to==who) continue;
		join[cnt]=rank[v];
		par_p[cnt]=belong[v];
		dfs(to,v);
	}
}
int sign[100005];
int get(int i){
	while(!del[i].empty() && !pq[i].empty() && pq[i].top()==del[i].top()){
		pq[i].pop();del[i].pop();
	}
	if(!pq[i].empty()) return pq[i].top();
	return INF;
}
pi tmp[25];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=0;i<n-1;++i){
		int a,b;scanf("%d%d",&a,&b);--a;--b;
		g[a].push_back(b);g[b].push_back(a);
	}
	prep(0,-1);
	par_p[0]=-1;join[0]=-1;
	dfs(0,-1);
	for(int hoge=0;hoge<q;++hoge){
		int t,i;scanf("%d%d",&t,&i);--i;
		if(t==0){
			if(sign[i]) del[belong[i]].push(i);
			else pq[belong[i]].push(i);
			sign[i]^=1;
		}else{
			int j=0;
			int cur=belong[i],pos=rank[i];
			while(cur!=-1){
				tmp[j++]=make_pair(cur,pos);
				pos=join[cur];
				cur=par_p[cur];
			}
			reverse(tmp,tmp+j);
			int suc=0;
			for(int k=0;k<j;++k){
				int t=get(tmp[k].first);
				if(t<INF && rank[t]<=tmp[k].second){
					suc=1;
					printf("%d\n",t+1);
					break;
				}
			}
			if(!suc) printf("-1\n");
		}
	}

	return 0;
}