思路：

树上倍增

anc[i][u]:u的2^i祖先

mx[i][u]:u到它的2^i祖先之间的最大值，不包括u

pre[i][u]:以u开始的递增序列的2^i祖先

sum[i][u]:以u开始递增序列从u到2^i祖先的和，不包括u

代码：

#include
     
      using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=4e5+5;const ll INF=1e15;int anc[20][N],pre[20][N];ll sum[20][N],w[N],mx[20][N];int main(){    ios::sync_with_stdio(false);    cin.tie(0);    cout.tie(0);    int q,cnt=1,op;    ll l,r,last=0;    w[0]=INF;    for(int i=0;i<20;i++)sum[i][1]=sum[i][0]=mx[i][1]=mx[i][0]=INF;    cin>>q;    while(q--){        cin>>op>>l>>r;        l^=last;        r^=last;        if(op==1){            anc[0][++cnt]=l;            w[cnt]=r;            mx[0][cnt]=w[l];            for(int i=1;i<20;i++){                anc[i][cnt]=anc[i-1][anc[i-1][cnt]];                mx[i][cnt]=max(mx[i-1][cnt],mx[i-1][anc[i-1][cnt]]);            }            int t=cnt;            for(int i=19;i>=0;i--){                if(mx[i][t]
      
       =0;i--){                    if(sum[i][l]<=r){                        r-=sum[i][l];                        l=pre[i][l];                        ans+=1<