これはあまり方針に迷わなかった。
https://yukicoder.me/problems/no/900
問題
根付き木が与えられる。
各辺には、長さが設定されている。
以下のクエリに順次答えよ。
- 頂点aのSubTree内の全辺に、長さをxずつ加算する
- 根頂点から頂点bへの長さを答える
解法
頂点vの根頂点からの距離をF(v)とし、(辺の長さを1とみなしたときの)頂点vの根からの深さをD(v)とする。
頂点aに対し前者のクエリを適用すると、SubTree内の頂点xに対してはF(x)はx*(D(v)-D(a))だけ加算される。
よって、F(v)をD(v)の1次関数とみなし、F(v)=A(v)*D(v)+B(v)としよう。
事前にオイラーツアーを行い頂点を並べ替えておくと、前者のクエリは区間に対しA(v)とB(v)に同じ値を加減算することになるので、A(v)とB(v)それぞれBITを持っておけばよい。
int N,Q; vector<pair<int,int>> E[101010]; ll D[101010]; int L[101010],R[101010]; int id; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} }; BIT<ll,20> bta,btb; void dfs(int cur,int pre,int d) { D[cur]=d; L[cur]=id++; FORR(e,E[cur]) if(e.first!=pre) { int pa=id; dfs(e.first,cur,d+1); bta.add(pa,e.second); bta.add(id,-e.second); } R[cur]=id; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) { cin>>x>>y>>r; E[x].push_back({y,r}); E[y].push_back({x,r}); } dfs(0,0,0); cin>>Q; while(Q--) { cin>>i; if(i==1) { cin>>x>>y; btb.add(L[x],y); btb.add(R[x],-y); bta.add(L[x],-D[x]*y); bta.add(R[x],D[x]*y); } else { cin>>x; cout<<bta(L[x])+D[x]*btb(L[x])<<endl; } } }
まとめ
区間加算の累積和問題は、SegTreeよりBIT派かな…。