最暴力的想法自然是，对于每一次询问，沿着父亲一点一点往上跳模拟。这样似乎并不能优化...

稍微好一点的想法是对于每一个点开一个nxt数组表示父亲中权值大于他的里面离他最近的在哪里，同样对于每一次询问模拟往上跳，每次加点模拟往上找，复杂度依旧没有变化，但为我们提供了一个思路，我们可以倍增啊！

首先我们对于2操作，我们记录sum[x][i]表示他的2^i个nxt的值的和是多少，这样我们就可以快速求出在总权值小于x的前提下最多能跳到哪里。

考虑如何求出这个数组。

定义nxt[x][i]为x的第2^i个nxt是谁。

对于每一次加点操作，我们记录fa[x][i]表示x的第2^i个父亲是谁，同时记录这些父亲中的最大值是多少。那么我们加入一个点时就可以快速求出第一个大于他的位置在哪里。即nxt[x][0],然后递推可以分别求出nxt[x][1],nxt[x][2].....沿途记录sum即可。

1 #include
      
        2 #define LL long long 3 using namespace std; 4 const int inf=4e5+10; 5 int Q,siz,last; 6 int w[inf]; 7 int fa[inf][20],Max[inf][20]; 8 int nxt[inf][20]; 9 LL sum[inf][20];10 void get(int x,int y){11     fa[x][0]=y;12     Max[x][0]=w[y];13     for(int i=1;i<=19;i++){14         fa[x][i]=fa[fa[x][i-1]][i-1];15         Max[x][i]=max(Max[x][i-1],Max[fa[x][i-1]][i-1]);16     }17     int now=x;18     for(int i=19;i>=0;i--){19         if(Max[now][i]
       
        y)return 0;31     int cnt=1;32     y-=w[x];33     for(int i=19;i>=0;i--){34         if(nxt[x][i]!=0&&sum[x][i]<=y){35             y-=sum[x][i];36             x=nxt[x][i];37             cnt+=p[i];38         }39     }40     return cnt;41 }42 int main()43 {44     scanf("%d",&Q);45     siz=1;46     p[0]=1;47     for(int i=1;i<=19;i++)p[i]=p[i-1]<<1;48     while(Q--){49         int opt;50         LL x,y;51         scanf("%d%lld%lld",&opt,&x,&y);52         x=x^last;y=y^last;53         if(opt==1){54             siz++;55             w[siz]=y;56             get(siz,x);57         }58         else {59             last=work(x,y);60             printf("%d\n",last);61         }62     }63     return 0;64 }