E. Gold Transfer（树上倍增）

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

#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; 
		}
	}	
}

最后

以上就是美丽眼睛为你收集整理的E. Gold Transfer（树上倍增）的全部内容，希望文章能够帮你解决E. Gold Transfer（树上倍增）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。