Codeforces932D. Tree

n<=400000个在线操作：树上插入一个某点权、父亲为某点的点；查询这样的最长点序列：序列的某个数必须是上一个数的祖先之一；序列的点权和不能超过x；序列的某个点的点权必须不小于上一个，且相邻两个点之间不存在点权大于等于深度大的那个点的点权的点。

说白了，就是每个点找他祖先中第一个点权大于等于他的点，然后建一棵假的树，树边表示某点如果要构造序列，序列的下一个数字就是他祖先。

分别处理：原树父亲、祖先点权最大值、假的树的父亲、假的树的祖先点权和，四个st表一个推一个即可。

//#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
//#include<map>
#include<math.h>
//#include<time.h>
//#include<complex>
#include<algorithm>
using namespace std;

int n;
#define maxn 400011
#define LL long long
LL fa[maxn][22],val[maxn],M[maxn][22],pp[maxn][22],sum[maxn][22],tot=1;

int main()
{
    scanf("%d",&n);
    int last=0; LL x,y,z;
    for (int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z); y^=last; z^=last;
        if (x==1)
        {
            val[++tot]=z;
            fa[tot][0]=y; for (int i=1;i<=20;i++) fa[tot][i]=fa[fa[tot][i-1]][i-1];
            M[tot][0]=max(val[y],z); for (int i=1;i<=20;i++) M[tot][i]=max(M[tot][i-1],M[fa[tot][i-1]][i-1]);
            if (val[y]>=z) pp[tot][0]=y;
            else
            {
                int t=y; for (int i=20;i>=0;i--) if (fa[t][i] && M[t][i]<z) t=fa[t][i]; t=fa[t][0];
                pp[tot][0]=t;
            }
            for (int i=1;i<=20;i++) pp[tot][i]=pp[pp[tot][i-1]][i-1];
            sum[tot][0]=val[tot]+val[pp[tot][0]];
            for (int i=1;i<=20;i++) sum[tot][i]=sum[tot][i-1]+sum[pp[tot][i-1]][i-1]-val[pp[tot][i-1]];
        }
        else
        {
            if (val[y]>z) {printf("%d\n",(last=0)); continue;}
            int t=y,ans=1; for (int i=20;i>=0;i--) if (pp[t][i] && sum[t][i]<=z) ans+=(1<<i),z-=sum[t][i]-val[pp[t][i]],t=pp[t][i];
            printf("%d\n",(last=ans));
        }
    }
    return 0;
}