AOJ 2170 Marked Ancestor ver.2
別解を友人に教えてもらった
1.逆からunionfind
2.Euler tour + BIT + doubling
については
http://sigma425.hatenablog.com/entry/2014/08/05/232421の通り.
3.(new)
Euler tour + segtree
それぞれのノードは"marked ancestorの候補"を持っている.
更新クエリ:in[v]~out[v]を覆うようなブロック達について,(まだ書き込まれていないor今書こうとしている値が既に書き込まれた値の子孫である)なら書き込む.
解答クエリ:in[v]のノードから上に0まで見ていって,最も子孫側を答える.
anc(x,y):xがyのancestor は in[x]<in[y]&&out[y]>out[x] とかける
コード見たほうがわかりやすそう.
正当性:
まず,in[v]の上にvの先祖以外が書き込まれてないことが,vを含む区間がin[x]~out[x]と表せるならxがvの先祖であることからわかる.
また,書き込まれた値は必ずin[v]の上のどこかにあり,そのうち直近のものは必ず残っている(rewriteされてない)ことがわかる.
#include <iostream> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) vector<int> G[100000],euler; const int p2=262144; int in[100000],out[100000],n,q; int seg[p2*2-1]; void dfs(int v){ in[v]=euler.size(); euler.push_back(v); rep(i,G[v].size()) dfs(G[v][i]); out[v]=euler.size(); euler.push_back(v); } bool anc(int x,int y){ return in[x]<in[y]&&out[x]>out[y]; } void change(int a,int b,int c,int l,int r,int k){ if(b<=l||r<=a) return; if(a<=l&&r<=b){ if(seg[k]==-1||anc(seg[k],c) ) seg[k]=c; return; } change(a,b,c,l,(l+r)/2,k*2+1); change(a,b,c,(l+r)/2,r,k*2+2); } int main(){ while(true){ cin >> n >> q; if(n==0) break; euler.clear(); rep(i,n) G[i].clear(); rep(i,p2*2-1) seg[i]=-1; rep(i,n-1){ int p; cin >> p; G[p-1].push_back(i+1); } dfs(0); long long ans=0; change(in[0],out[0]+1,0,0,p2,0); rep(i,q){ char c; int v; cin >> c >> v; v--; if(c=='M'){ change(in[v],out[v]+1,v,0,p2,0); }else{ int x=p2-1+in[v],ret=0; while(true){ if(seg[x]!=-1 && anc(ret,seg[x])) ret=seg[x]; if(x==0) break; x=(x-1)/2; } ans+=(ret+1); } } cout << ans << endl; } }