Codeforces ECR #110 : E. Gold Transfer

F問題が急に難しくなった回。
https://codeforces.com/contest/1535/problem/E

問題

根付き木を考える。
各頂点vには、A[v]の量の金が埋まっており、その価格はC[v]である。
初期状態で根付き木はroot頂点のみである。
以下のクエリに順次答えよ。

• 根付き木で、新規の点cを既存の頂点vの子頂点として追加する。この時、C[v]＜C[c]である。
• 点vと重量wが指定される。rootからvの頂点上にある金を、総量wに至るまで価格の安い順に回収する。回収した金の量とその価格を求めよ。

解法

前者のクエリに対しては、頂点を追加するたびに親頂点をダブリングしよう。
後者にクエリについて、C[v]＜C[c]の条件より、常に親頂点から先に金を回収する。
そこでダブリングした親頂点情報を用いて、金が残っている最も根頂点寄りの点を求め、そこから金を回収すればよい。

int Q;
int N;
ll A[303030],C[303030];
int P[303030][20];
int V;
ll W;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q>>A[0]>>C[0];
	for(i=1;i<=Q;i++) {
		cin>>x;
		if(x==1) {
			cin>>P[i][0]>>A[i]>>C[i];
			FOR(j,19) P[i][j+1]=P[P[i][j]][j];
			
		}
		else {
			cin>>V>>W;
			ll sum=0,sc=0;
			
			while(W&&A[V]) {
				int tar=V;
				for(j=19;j>=0;j--) if(A[P[tar][j]]) tar=P[tar][j];
				ll a=min(W,A[tar]);
				sum+=a;
				sc+=a*C[tar];
				A[tar]-=a;
				W-=a;
			}
			cout<<sum<<" "<<sc<<endl;
		}
	}
}

まとめ

オンラインでダブリングしていくの割と珍しいかも。