首先有个动态加叶子的操作，考虑到树剖需要离线下来预处理，便考虑用倍增来维护。
首先要找到 \(\ge a_u\) 的最深的父亲 \(v\)，便可以先用倍增处理好长度为 \(2^i\) 的链上的 \(\max\)。
如果 \(\max < a_u\)，就往上跳，跳不了就是到点 \(v\) 了。
考虑连边 \(v\to u\)，这仍然会是一棵树（建个虚根为 \(0\)）。
于是可以考虑在这棵树上再维护一个 \(2^i\) 长度的链的 \(\sum\)。
如果 \(W\ge sum\) 就可以往上跳并减掉 \(sum\)。
时间复杂度 \(O(n\log n)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
const i64 inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 4e5 + 10, maxm = 20;
int fa[maxn][maxm], mx[maxn][maxm];
int fas[maxn][maxm]; i64 sum[maxn][maxm];
inline i64 Sum(i64 a, i64 b) {return std::min(a + b, inf);}
int main() {
int Q; scanf("%d", &Q);
int n = 1, ans = 0;
for (int i = 0; i < maxm; i++) sum[0][i] = inf;
for (int i = 1; i < maxm; i++) sum[1][i] = inf;
auto jmp = [&](int u, int v) {
for (int i = maxm - 1; ~ i; i--) mx[u][i] < v && (u = fa[u][i]);
return u;
};
while (Q--) {
int op; scanf("%d", &op);
if (op == 1) {
int f, w; scanf("%d%d", &f, &w);
f ^= ans, w ^= ans;
n++;
mx[n][0] = w, sum[n][0] = w, fa[n][0] = f;
for (int i = 1; i < maxm; i++) fa[n][i] = fa[fa[n][i - 1]][i - 1], mx[n][i] = std::max(mx[n][i - 1], mx[fa[n][i - 1]][i - 1]);
fas[n][0] = jmp(f, w), sum[n][0] = w;
for (int i = 1; i < maxm; i++) fas[n][i] = fas[fas[n][i - 1]][i - 1], sum[n][i] = Sum(sum[n][i - 1], sum[fas[n][i - 1]][i - 1]);
} else {
int u; i64 w; scanf("%d%lld", &u, &w);
u ^= ans, w ^= ans;
ans = 0;
for (int i = maxm - 1; ~ i; i--) w >= sum[u][i] && (ans |= 1 << i, w -= sum[u][i], u = fas[u][i]);
printf("%d\n", ans);
}
}
return 0;
}