E. Gold Transfer（树上倍增）

109 阅读 0 评论 72 点赞

我是靠谱客的博主美丽眼睛，这篇文章主要介绍E. Gold Transfer（树上倍增），现在分享给大家，希望可以做个参考。

根据题意离根越近的金子就越便宜，注意存在一个金子卖完的情况，显然对于每次询问w,v，我们可以从v这个点向根的方向找，找到最后一个可以有金子的节点然后买金子，然后继续循环往复即可。想上寻找的过程我们可以用倍增优化时间复杂度。
AC代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N=3e5+5;
int n;
int a[N],c[N];
int f[N][22];
 
main(){
	cin>>n>>a[0]>>c[0];
	
	for(int i=1;i<=n;i++){
		int op;
		cin>>op;
		if(op==1){
			int p;
			cin>>p>>a[i]>>c[i];
			f[i][0]=p;
			for(int j=1;j<=20;j++)f[i][j]=f[f[i][j-1]][j-1];
		}
		else{
			int v,w;
			cin>>v>>w;
			
			int cnt=0,cost=0;
		
			while(w&&a[v]>0){
				int u=v;
				for(int j=20;j>=0;j--)if(a[f[u][j]]>0)u=f[u][j];
				
				int k=min(w,a[u]);
				w-=k,a[u]-=k;
				cnt+=k,cost+=k*c[u];
			}
			
			cout<<cnt<<" "<<cost<<endl; 
		}
	}	
}