AOJ 2170 Marked Ancestor
問題:
N頂点の根付き木,Q個のクエリ
クエリM v:頂点vを塗る
クエリQ v:頂点v以上で塗られている最も近いindexを答える
はじめは頂点1(root)だけが塗られている
N,Q<=10^5
文句:
問題文が意味不明(説明が足りなすぎる)
クエリQの原文は
Q v: (Query) Print the index of the nearest marked ancestor of node v which is nearest to it.
なのだが、これで自分自身を含むと誰が思えるんだろう
解法:
euler tour 1D版 + doubling + BIT でやった。
dbl[i][j]=頂点iから1くくj個上の頂点(不等号*2だとコメントアウトされる)
とeuler tourの配列を持っておき、マークするクエリにはeuler tourの入っていく方に+1,出てくほうに-1足す。答えるクエリは「1~vまで(の経路)で何個塗られてるか」がわかれば、doublingでにぶたんすればわかる。「」の中はBITでもてばよい。(euler tourの良い性質(関係ないところは+1と-1が打ち消し合う)を使っている)
のだが、もっと簡単な解法があった
先にMarkクエリを全部処理したと考えて、逆から見ていくと、そこで併合すればいいのでUnionFindでいける。ただし何回も同じ場所にmarkされる場合があることに注意(これも制約からは読み取れない,これは意地が悪い程度のレベルだと思う)
ミス:
long longにするのを忘れた
my code:
#include <iostream> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) vector<int> G[100000],euler; int dbl[100000][18],ff[100000],ss[100000],bit[200001],n,q; int sum(int i){ int s=0; while(i>0){ s+=bit[i]; i-= i&-i; } return s; } void add(int i,int x){ while(i<=2*n){ bit[i]+=x; i+= i&-i; } } void dfs(int v){ ff[v]=euler.size(); euler.push_back(v); rep(i,G[v].size()) dfs(G[v][i]); ss[v]=euler.size(); euler.push_back(v); } int main(){ while(true){ cin >> n >> q; if(n==0) break; euler.clear(); rep(i,n) G[i].clear(); rep(i,n) rep(j,18) dbl[i][j]=-1; rep(i,2*n+1) bit[i]=0; rep(i,n-1){ int p; cin >> p; G[p-1].push_back(i+1); dbl[i+1][0]=p-1; } rep(i,17){ rep(j,n){ if(dbl[j][i]==-1) dbl[j][i+1]=-1; else dbl[j][i+1]=dbl[dbl[j][i]][i]; } } dfs(0); add(ff[0]+1,1); add(ss[0]+1,-1); long long ans=0; rep(i,q){ char c; int v; cin >> c >> v; v--; if(c=='M'){ add(ff[v]+1,1); add(ss[v]+1,-1); }else{ int x=sum(ff[v]+1); for(int j=17;j>=0;j--){ if(dbl[v][j]!=-1 && sum(ff[dbl[v][j]]+1)>=x) v=dbl[v][j]; } ans+=(v+1); } } cout << ans << endl; } }