题目链接

题意

节点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;
}