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