Eと比べこちらは実装重め。
http://codeforces.com/contest/893/problem/F
問題
N頂点の根付き木が与えられる。
各頂点には整数値が振られている。
この木に関し以下のM個のクエリに答えよ。
クエリは頂点XとパラメータKで設定される。
XのSubTree内でXからの距離がK以下の頂点のうち、振られた整数値の最小値を求めよ。
解法
RMQとダブリングで解く。
まず、各頂点についてダブリングの要領でSubTree内における自身から距離2^0、2^1、2^2、…以内の頂点の値の最小値を求めよう。
各クエリに関して複数のKが2の累乗のクエリに分解して解く。
例えばK=10=1010bだとする。
まずXからは距離8以内の頂点に関して、先のダブリングの結果を用いて最小値を得る。
あとは距離9,10の対処だが、Xから距離8の頂点群に対し、それぞれさらに距離2の範囲の最小値を求め、その全体の最小値を求めればよい。
このためには、Xから距離8の頂点群に対しRMQを求められるようにデータ構造を組んでおく必要がある。
これは幅優先探索で頂点にIDを振っていくと、対象の頂点群が連番になるのでRMQが適用できるようになる。
また、EulerTour順のIDも別途保持しておくと、RMQにおける探索範囲も高速に求められる。
RMQをSegTreeで処理する場合、各クエリに関し、RMQをlog(K)回行うのと、その都度EulerTourからの探索範囲検索とRMQがいずれもO(logN)かかる。
ダブリングがO(NlogN)、RMQ構築がO(Nlog^2N)、クエリ処理がO(MlogKlogN)かな。
int N,root,M; int A[101010]; int X,K; template<class V,int NV> class SegTree_1 { public: vector<V> val; static V const def=1<<30; V comp(V l,V r){ return min(l,r);}; SegTree_1(){val=vector<V>(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y if(r<=x || y<=l) return def; if(x<=l && r<=y) return val[k]; return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); } void update(int entry, V v) { entry += NV; val[entry]=v; while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_1<int,1<<18> dst[21]; int id=1; int D[101010]; int L[101010]; int R[101010]; int P[20][101010]; int dmi[20][101010]; int ID[101010]; int rev[101010]; vector<pair<int,int>> V[201010]; vector<int> E[101010]; void dfs(int cur,int pre,int d) { P[0][cur]=pre; if(pre==-1) P[0][cur]=cur; D[cur]=d; rev[id]=cur; L[cur]=id; V[d].push_back({id,0}); id++; FORR(e,E[cur]) if(e!=pre) dfs(e,cur,d+1); R[cur]=id; } void solve() { int i,j,k,l,r,x,y; string s; scanf("%d%d",&N,&root); root--; FOR(i,N) { scanf("%d",&A[i]); FOR(j,20) dmi[j][i]=A[i]; } FOR(i,N-1) { scanf("%d%d",&x,&y); E[x-1].push_back(y-1); E[y-1].push_back(x-1); } dfs(root,-1,0); id=1; FOR(i,N+1) { FORR(v,V[i]) ID[rev[v.first]]=v.second=id++; } FOR(j,N) { dmi[0][P[0][j]]=min(dmi[0][P[0][j]],A[j]); } FOR(i,19) { FOR(j,N) { P[i+1][j]=P[i][P[i][j]]; dmi[i+1][j]=min(dmi[i+1][j],dmi[i][j]); dmi[i+1][P[i][j]]=min(dmi[i+1][P[i][j]],dmi[i][j]); } FOR(j,N) dst[i].update(ID[j],dmi[i][j]); } int ret=0; scanf("%d",&M); while(M--) { scanf("%d%d",&X,&K); X=(X+ret)%N; K=(K+ret)%N; ret=A[X]; int TL=L[X],TR=R[X]; int dep=D[X]; for(j=18;j>=0;j--) if(K&(1<<j)) { auto it=lower_bound(ALL(V[dep]),make_pair(L[X],0)); auto it2=lower_bound(ALL(V[dep]),make_pair(R[X],0)); if(it!=it2) { it2--; x=it->second; y=it2->second+1; ret=min(ret,dst[j].getval(x,y)); } dep+=1<<j; } _P("%d\n",ret); } }
まとめ
実装はともかく、わかってしまえばアイデアはそれほど複雑ではない。