本番にかなりさっくり解いてる。
https://codeforces.com/contest/1891/problem/F
問題
根付き木を考える。各点には整数値が設定される。
初期状態では根の頂点のみである。
以下のクエリを順次処理したとき、最終的に各点の設定値を答えよ。
- 木に点を追加する。その点の設定値は0となる。
- 点vのsubtreeにxを加算する。
解法
先にクエリを先読みし、木を構築してDFS順で点を並べておく。
あとは、区間加算・区間乗算ができるSegTreeでクエリを処理して行く。
後者のクエリは区間加算すればよいし、頂点が追加された段階で、区間乗算で0を掛ければ、新設の点の設定値はそれまでの加算分を無視できる。
template<class V,int NV> class SegTree_MulAdd { public: vector<V> sum,mul,add; // sum stores val after muladd SegTree_MulAdd(){sum.resize(NV*2,0); mul.resize(NV*2,1); add.resize(NV*2,0);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l) return 0; if(x<=l && r<=y) return sum[k]; x=max(x,l); y=min(y,r); V ret=getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1); return ret*mul[k]+add[k]*(y-x); } void propagate(int k,int s) { mul[k*2]*=mul[k]; add[k*2]*=mul[k]; sum[k*2]*=mul[k]; add[k*2]+=add[k]; sum[k*2]+=add[k]*s/2; mul[k*2+1]*=mul[k]; add[k*2+1]*=mul[k]; sum[k*2+1]*=mul[k]; add[k*2+1]+=add[k]; sum[k*2+1]+=add[k]*s/2; mul[k]=1; add[k]=0; } void domul(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { mul[k]*=v; add[k]*=v; sum[k]*=v; } else if(l < y && x < r) { propagate(k,r-l); domul(x,y,v,l,(l+r)/2,k*2); domul(x,y,v,(l+r)/2,r,k*2+1); sum[k]=sum[k*2]+sum[k*2+1]; } } void doadd(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { add[k]+=v; sum[k]+=(r-l)*v; } else if(l < y && x < r) { propagate(k,r-l); doadd(x,y,v/mul[k],l,(l+r)/2,k*2); doadd(x,y,v/mul[k],(l+r)/2,r,k*2+1); sum[k]=sum[k*2]+sum[k*2+1]; } } }; SegTree_MulAdd<ll, 1<<19> st; int id,L[505050],R[505050]; vector<int> C[505050]; int T,Q; int t[505050],V[505050],X[505050]; void dfs(int cur) { L[cur]=id++; FORR(e,C[cur]) dfs(e); R[cur]=id; } void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { st.domul(0,1<<19,0); cin>>Q; FOR(i,Q) { C[i].clear(); } int sz=1; FOR(i,Q) { cin>>t[i]>>V[i]; V[i]--; if(t[i]==1) { X[i]=sz; C[V[i]].push_back(sz++); } else { cin>>X[i]; } } id=0; dfs(0); FOR(i,Q) { if(t[i]==1) { st.domul(L[X[i]],R[X[i]],0); } else { st.doadd(L[V[i]],R[V[i]],X[i]); } } FOR(i,sz) cout<<st.getval(L[i],L[i]+1)<<" "; cout<<endl; } }
まとめ
2250ptとはいえ、なんでこれFに置いたんだろ。