Tree

• 翻译(qwq,看了好久的题)

输入n组数据,p,x,y,将其处理为x^=las,y^=las,las是上一次输出的答案，初始为1

1. 1 x y 将一个权值为y的新节点加到x节点的后面

2. 2 x y 求从点x到根节点的路径上求出最长的不下降子序列，且满足它的和不大于y(像下面这样)

• 分析

  首先是因为他既可能加到1,节点后面，也可能会加到0节点后面，很难确定谁是根节点，所以在处理的时候，将所有询问的x统统加1。

  对于二操作，因为他要求从一个节点到根节点的最长不下降子序列，那么说明在x点之前权值小于y的点都没用，那这时候我们就找到第一个权值大于等于y的节点，并将它作为x的父亲，维护他们的前缀和

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

/*真正的"树剖"大法*/
#include<bits/stdc++.h>

#define R register
#define ll long long

using namespace std;

const int N=4e5+10;
const ll inf=1e18+2;

ll cnt=2,q,las;
ll sum[N],f[21][N],k[N];

int main()
{
    scanf("%lld",&q);
    sum[1]=inf;k[1]=inf;sum[2]=inf;
    f[0][2]=1;
    for (int o=1;o<=q;o++)
    {
        ll p,x,y;
        scanf("%lld%lld%lld",&p,&x,&y);
        x^=las,y^=las;
        //本次的询问
        if(p==1)
        {
            ++cnt;x++;
            //x是节点,y是权重 
            if(k[x]<y)
            {
                for (int i=19;i>=0;i--)
                    if(f[i][x]&&k[f[i][x]]<y) x=f[i][x];
                x=f[0][x];
            }

            k[cnt]=y;
            f[0][cnt]=x;
            sum[cnt]=y+sum[x];

            for (int i=1;i<=19;i++)
                f[i][cnt]=f[i-1][f[i-1][cnt]];
        }//加点
        else
        {
            ll ans=0;x++;
            for (int i=19;i>=0;i--)
                if(f[i][x]&&sum[x]-sum[f[i][x]]<=y)
                    ans+=(1<<i),y-=(sum[x]-sum[f[i][x]]),x=f[i][x];

            printf("%lld\n",ans);
            las=ans;
        }//查询 
    }

    return 0;
}