题意

给你一棵树，要你实现两个操作，且强制在线。

• 在新建一个节点链接到原有节点。
• 查询当前节点 到根节点有多少个值大于等于 的，且路径长度小于一定值 。

  分析

  如果我们暴力求解。那么插入节点的时间复杂度为 ，查询操作的时间复杂度为 。考虑平衡时间复杂度。因为是没有修改操作的，那么当插入一个节点之后这个节点到根节点的路径就确定了。考虑优化暴力走父亲的过程。定义 是节点 的应该走的第 节点， 是 到 的路径长度。那么只需要在插入一个节点时更新它的倍增数组就好了，时间复杂度 。查询的复杂度为 。讨论一下定值 和 的关系就好了。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  #define LL long long
  LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
  } 
  const LL N = 4e5+100,inf = 0x3f3f3f3f3f3f3f3f;
  LL val[N],fa[N][21],s[N][21],si = 1,ans = 0,Q;
  void add(LL x,LL f) {
    if(val[f] >= val[x]) fa[x][0] = f;
    else {
        for(int i = 19;~i;i--) if(val[fa[f][i]] < val[x]) f = fa[f][i];
        fa[x][0] = fa[f][0];
    } 
    s[x][0] = val[fa[x][0]];
    for(int i = 1;i <= 19;i++) {
        fa[x][i] = fa[fa[x][i-1]][i-1];
        if(!fa[x][i]) s[x][i] = inf;
        else s[x][i] = (s[fa[x][i-1]][i-1] + s[x][i-1]) >= inf?inf:(s[fa[x][i-1]][i-1]+s[x][i-1]);
    }
  } 
  LL ask(LL x,LL tot) {
    if(tot-val[x] < 0) return 0;
    LL Ans = 1;tot -= val[x];
    for(int i = 19;~i;i--) if(tot >= s[x][i]) tot -= s[x][i],x = fa[x][i],Ans = (Ans+(1<<i));
    return Ans;
  }
  int main() {
    val[0] = inf;
    memset(s[1],0x3f,sizeof(s[1]));memset(s[0],0x3f,sizeof(s[0]));
    Q = read();
    while(Q--) {
        int opt = read();LL R = read()^ans,W = read()^ans;
        if(opt == 1) {
            val[++si] = W;
            add(si,R);
        }
        else {
            ans = ask(R,W);
            printf("%lld\n",ans);
        }
    }
  }