当前位置：网站首页>Gold Transfer（树上倍增）

Gold Transfer（树上倍增）

2022-08-11 10:23:00 【Here_SDUT】

题目链接

题意

节点0为根节点，有 a_0 吨黄金， 每吨黄金价格为 c_0，现在有 q 次操作，每次操作有两种类型：

  • 在 p_i 节点下新增一个节点，编号为 i (对应第 i 次操作)，该节点有 a_i 吨黄金， 每吨黄金价格为 c_i，保证子节点的黄金单价比父节点的高。
  • 从 v_i 到0节点的最短路径上购买 w_i 吨黄金，如果路径上的黄金不够则全部购买，求最少花费。

题目要求用在线的方式解决问题，每次输出答案后需要刷新操作。

分析

对于一棵有根树，每个节点到根节点的最短路径唯一确定，并且由于子节点的黄金单价比父节点高，为了使得花费最少，我们要尽量从靠近父节点的地方购买黄金。暴力的做法是每次从 v_i 向上走到根节点找到最短路径，然后再向下挨个购买。最坏时间复杂度为 O(q^2) 。

我们可以用树上倍增的思想解决这个问题：

  • 对于每次查找操作： 每次找到最短路径上离根节点最近的剩余黄金量不为0的点，其实就是找离 v_i 最远的 u ,且 a[u] != 0。然后min(need, a[u]) 那么多的黄金，need指当前还需要的黄金量，更新a[u]和need的值。然后进行新一轮的查找，再进行购买，直到need为0，或者整条路径上没有黄金为止(可以通过a[v]是否为0判断)。
  • 对于插入节点操作(将v作为p的一个儿子)： 设 fa[v][k] 表示节点v的第 2^k 辈祖先，则fa[v][0] = p ，即 v 的父亲节点为 p ，再通过递推式 fa[v][k] = fa[fa[v][k-1]][k-1] 可以处理出 v 的每个2的幂次辈祖先。

总时间复杂度为 O(qlog(q))。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 3e5+10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
int fa[maxn][25],a[maxn], c[maxn];
int main(int argc, char const *argv[]) {
    int q;
    cin >> q >> a[0] >> c[0];
    for(int id = 1; id <= q; id++) {
        int op;scanf("%d",&op);
        if(op == 1) {
            int p;
            cin >> p >> a[id] >> c[id];
            fa[id][0] = p;
            for(int i = 1; i <= 20; i++) {
                fa[id][i] = fa[fa[id][i-1]][i-1];
            }
        }else {
            int v, need;
            cin >> v >> need;
            int now = v, len = 20;
            int ans1 = 0;
            LL ans2 = 0;
            while(need > 0 && a[v] > 0) {
                int u = v;
                for(int k = 20; k >= 0; k--) {
                    if(a[fa[u][k]] > 0) u = fa[u][k];
                }
                int can = min(need,a[u]);
                need -= can;
                a[u] -= can;
                ans1 += can;
                ans2 += (LL)can*c[u];
            }
            cout << ans1 << ' ' << ans2 << endl;
        }
    }
    return 0;
}
原网站

版权声明
本文为[Here_SDUT]所创，转载请带上原文链接，感谢
https://cloud.tencent.com/developer/article/2070239

边栏推荐

猜你喜欢

随机推荐