我是靠谱客的博主 美丽眼睛,这篇文章主要介绍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.内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(60)

评论列表共有 0 条评论

立即
投稿
返回
顶部