分析

首先，此题需要加点和查询操作
我们可以想到倍增
但由于对于祖先的选择有要求
所以我们需要修改对于倍增数组的表示
Anc[i][j]表示从点向上走个满足要求的点之后，到达的点
Sum[i][j]表示从点向上走个满足要求的点得权值之和
这样我们就可以查询了
至于插入操作
我们需要先求出此点祖先中第一个满足要求的祖先
我们也可以直接得到

时间复杂度：

代码

//CF932D
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(LL i=Head[A];i;i=Next[i])
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const LL MAXN=4e5+10;

LL Size=1,Total,Opt,u,v,w,Test,Last;
LL Num[MAXN];
LL Anc[MAXN][21],Sum[MAXN][21];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Update(LL New,LL Pre) {
    if(Num[Pre]>=Num[New]) Anc[New][0]=Pre,Sum[New][0]=Num[Anc[New][0]];
    else {
        BOR(i,20,0) if(Num[Anc[Pre][i]]<Num[New]) Pre=Anc[Pre][i];
        Anc[New][0]=Anc[Pre][0];
        Sum[New][0]=Num[Anc[New][0]];
    }
    FOR(i,1,20) {
        Anc[New][i]=Anc[Anc[New][i-1]][i-1];
        if(Sum[New][i-1]==INF) Sum[New][i]=INF;
        else Sum[New][i]=Sum[New][i-1]+Sum[Anc[New][i-1]][i-1];
    }
}

inline LL Get(LL New,LL Limit) {
    if(Num[New]>Limit) return (LL)0;
    Limit-=Num[New];
    LL Res=0;
    BOR(i,20,0) 
        if(Sum[New][i]<=Limit) { Limit-=Sum[New][i]; New=Anc[New][i]; Res+=(1<<i); }
    return Res+1;
}

signed main() {
    //File();
    scanf("%lld",&Test);
    Num[0]=INF;
    Cl(Sum[1],0x3f);
    while(Test--) {
        scanf("%lld %lld %lld",&Opt,&u,&v);
        u^=Last; v^=Last;
        if(Opt==1) Num[++Size]=v,Update(Size,u);
        else printf("%lld\n",Last=Get(u,v));
    }
    //fclose(stdin); fclose(stdout);
    system("pause");
    return 0;
}