Codeforces E. Gold Transfer

本文主要是介绍Codeforces E. Gold Transfer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接http://codeforces.com/contest/1535/problem/E

题意：

一开始只有一个0号根节点节点，并且告诉你$a_0,c_0$表示0号节点上面的金块个数以及单个金块的价格，现在有q次操作
操作1：给你$p_i，a_i，c_i$，新的i号节点加入到pi节点的儿子节点，i号节点上面有ai个金块，以及每个金块的价格ci(保证$c_i>c_{pi}$)
操作2：给你一个$v_i，w_i$，让你从$v_i$到0号根节点的路径上买$w_i$个金块，如果可以购买到$w_i$个金块，则使用的最低价钱，如果买不到$w_i$块金牌，那么能买多少买多少，最后输出购买的金块数量和使用的价钱

思路：

首先题目中有一个关键条件$c_i>c_{pi}$，那么说明一条链上，从上到下，节点的金块单价在增高，所以我们对于询问操作，从$v_i到根节点路径上购买金块，优先考虑从根节点向下购买，先把便宜的金块购买了$
所以我们不难发现一条点到根节点的链上，越靠上的点的金块一定最先被购买完，所以我们对于一个询问，只需要找到$v_i到根节点的链上最上面第一个ci不为0的点作为购买的起始点向下购买就行，如何去找这个点呢？$
因为一条到根节点的路径上$ci$为0的节点一定是从根节点开始并且是连续的
所以我们使用树上倍增就可以$logq$找到这个点，对于q次询问总的复杂度就是$qlogq$

AC_Code:

#include<bits/stdc++.h>
using namespace std;
const int Maxn = 3e5+10;
typedef long long ll;
vector<int>p[30];//p[k][id]离id距离为2^k的点 
int a[Maxn],c[Maxn];
int main(){int q;cin>>q>>a[0]>>c[0];for(int i=0;i<30;i++) p[i].resize(Maxn);for(int i=0;i<30;i++) p[i][0] = 0;int kcase = 0;while(q--){++kcase;int op;cin>>op;if(op==1){int fa,ai,ci;cin>>fa>>ai>>ci;a[kcase] = ai;c[kcase] = ci;p[0][kcase]=fa;//树上倍增,路径从上到下找第一个权值不为0的节点 for(int k=1;k<30;k++){p[k][kcase] = p[k-1][p[k-1][kcase]];}}else{int w,v;ll ansm = 0,anss = 0;cin>>v>>w;while(w>0&&a[v]>0){int u = v;for(int i=29;i>=0;i--){if(a[p[i][u]]) u=p[i][u];}int need = min(w,a[u]);a[u]-=need;w-=need;ansm+=1ll*need*c[u];anss+=need;}cout<<anss<<' '<<ansm<<'\n';}}return 0;
}

这篇关于Codeforces E. Gold Transfer的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---