本番方針はわかったけどバグが取れず時間切れ。
http://kupc2015.contest.atcoder.jp/tasks/kupc2015_j
問題
N頂点の木を成す無向グラフが与えられる。
各頂点iには整数A[i]が振られている。
この木に対し、以下のクエリQ個に答えよ。
j番目のクエリは頂点対U[j],V[j]及び整数X[j]からなる。
U[j]からV[j]に至る最短パス上の各頂点vについて、X[j] %= A[v]で順次剰余を取った最終的な値を答えよ。
解法
考え方としては、TCO R2Aの問題が近い。
TopCoderOpen 2015 Round2A Easy ModModMod - kmjp's blog
各クエリの値X[j]を全部まとめてU[j]→LCA(U[j],V[j])と一旦LCAまで上に移動し、その後LCA(U[j],V[j])→V[j]と降ろしていくことを考える。
上への移動パートでは、各頂点で(現在のX[j], クエリ番号j)のsetを持ち、(現在のX[j])が今いる頂点vにおけるA[v]以上のものは適宜剰余を取る。
上にsetの要素を移動する際は、マージテクを用いてsetの要素のコピーが生じないようにする。
下に移動するときも、同様にset内で値が大きいX[j]をA[v]で割っていく。
下に移動する際はマージテクの逆に分割する必要があるので、どのsubtreeに何個クエリの要素が含まれるかも計算しておくと良い。
int N,Q; int A[101010]; int B[101010]; int C[101010]; int X[101010],V[101010],W[101010],LC[101010]; int OL[101010],OR[101010],eid; int P[21][100005],D[100005]; vector<int> E[101010]; vector<int> QS[101010],QL[101010],QE[101010]; vector<int> DV[101010]; set<pair<int,int>> S[101010]; int nt[101010],nt2[101010]; set<pair<int,int> > SV; void dfs(int cur) { OL[cur]=eid++; nt[cur]=QE[cur].size(); DV[D[cur]].push_back(cur); ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it), nt[cur]+=nt[*it]; OR[cur]=eid; } int lca(int a,int b) { int ret=0,i,aa=a,bb=b; if(D[aa]>D[bb]) swap(aa,bb); for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb]; for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb]; return (aa==bb)?aa:P[0][aa]; // vertex } void gomod(int r) { while(S[r].size()) { auto it=S[r].end(); int q=(*--it).second; if(X[q]<A[r]) break; X[q] %= A[r]; S[r].erase(it); S[r].insert({X[q],q}); } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N) cin>>A[i]; FOR(i,N-1) { cin>>B[i]>>C[i]; E[B[i]-1].push_back(C[i]-1); E[C[i]-1].push_back(B[i]-1); } dfs(0); FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]]; FOR(i,Q) { cin>>X[i]>>V[i]>>W[i]; V[i]--,W[i]--; LC[i]=lca(V[i],W[i]); QS[V[i]].push_back(i); QL[LC[i]].push_back(i); QE[W[i]].push_back(i); SV.insert({OL[W[i]],i}); } for(i=N;i>=0;i--) FORR(r,DV[i]) { int mav=-1, tar=-1; FORR(e,E[r]) if(D[e]==D[r]+1 && (int)S[e].size()>mav) mav=S[e].size(),tar=e; if(mav>=0) { swap(S[r],S[tar]); FORR(e,E[r]) if(D[e]==D[r]+1 && e!=tar) { FORR(ss,S[e]) S[r].insert(ss); S[e].clear(); } } FORR(q,QS[r]) S[r].insert({X[q],q}); gomod(r); FORR(q,QL[r]) S[r].erase({X[q],q}); } FOR(i,N+1) FORR(r,DV[i]) { FORR(q,QL[r]) S[r].insert({X[q],q}); gomod(r); FORR(q,QE[r]) S[r].erase({X[q],q}),SV.erase({OL[W[q]],q}); int mav=-1, tar=-1; FORR(e,E[r]) if(D[e]==D[r]+1 && nt[e]>mav) mav=nt[e],tar=e; FORR(e,E[r]) if(D[e]==D[r]+1 && tar!=e) { for(auto sit=SV.lower_bound({OL[e],0});sit!=SV.end() && sit->first<OR[e];sit++) { int ss=sit->second; if(S[r].count({X[ss],ss})) S[e].insert({X[ss],ss}), S[r].erase({X[ss],ss}); } } if(tar!=-1) swap(S[tar],S[r]); } FOR(i,Q) _P("%d\n",X[i]); }
まとめ
本番は下りのマージテク(分解テク?)でバグを入れてしまい間に合わず…もったいない。