题意

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

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

    分析

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

    代码

    #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);
          }
      }
    }