题目链接
题意
节点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))。
代码
代码语言：javascript复制#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;
}
