赛事 15+40+0

T2没开unsigned long long 100——>40痛失 sub 6

T1：莫反，不会

T2：本质是区间线性基，构造线性基的时候用对于一个位置用val（编号大的）大的代替val小的，val小的继续下放，其它跟正常线性基一样

这是一种贪心的算法，保证这个位置上保留的是最可能被取到（有贡献）的

#include<bits/stdc++.h>
using namespace std;
unsigned long long a[1000005],lw,ans;
unsigned long long n,m,cnt,type,aa,bb,mi[21],op,sum;
int f[1000005][21],head[1000005],nex[1000005],u[1000005],v[1000005],cc,dep[1000005],lpos;
void add(int uu,int vv)
{
    cc++;
    u[cc]=uu,v[cc]=vv;
    nex[cc]=head[u[cc]];
    head[u[cc]]=cc;
}
struct dd
{
    unsigned long long p[65];
    int pos[65];
}d[1000005];
void build(int x,int deep)
{
    deep++;
    dep[x]=deep;
    lw=a[x];
    lpos=dep[x];
//  cout<<x<<" "<<lw<<endl;
    for(long long i=63;i>=0;i--)
    {
//      if(i==2)
//      {
//          cout<<lw<<" "<<endl;
//      }
        if((lw&(1ULL<<i))>=1)
        {
            if(d[x].p[i]==0)
            {
                d[x].p[i]=lw;
                d[x].pos[i]=lpos;
                break;
            }
            else
            {
                if(d[x].pos[i]<lpos)
                {
                    swap(d[x].pos[i],lpos);
                    swap(d[x].p[i],lw);
                }
                lw=lw^d[x].p[i];
            }
        }
    }
    for(int j=1;j<=20;j++)
    {
        f[x][j]=f[f[x][j-1]][j-1];
    }
    int to;
    for(int i=head[x];i!=0;i=nex[i])
    {
        to=v[i];
        for(int j=0;j<=64;j++)
        {
            d[to].p[j]=d[x].p[j];
            d[to].pos[j]=d[x].pos[j];
        }
        build(to,deep);
    }
}
void ins(int ff,int x)
{
    dep[x]=dep[ff]+1;
    lw=a[x];
    lpos=dep[x];
    for(int j=0;j<=64;j++)
    {
        d[x].p[j]=d[ff].p[j];
        d[x].pos[j]=d[ff].pos[j];
    }
    for(long long i=63;i>=0;i--)
    {
        if((lw&(1ULL<<i))>=1)
        {
            if(d[x].p[i]==0)
            {
                d[x].p[i]=lw;
                d[x].pos[i]=lpos;
                break;
            }
            else
            {
                if(d[x].pos[i]<lpos)
                {
                    swap(d[x].pos[i],lpos);
                    swap(d[x].p[i],lw);
                }
                lw=lw^d[x].p[i];
            }
        }
    }
    for(int j=1;j<=20;j++)
    {
        f[x][j]=f[f[x][j-1]][j-1];
    }   
}
int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
//  int hhh=7&4;
//  cout<<hhh<<endl;
    mi[0]=1;
    for(int i=1;i<=20;i++)
    {
        mi[i]=mi[i-1]*2;
    }
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&f[i][0]);
        cin>>a[i];
        add(f[i][0],i);
    }
    cnt=n;
    build(1,0);
//  for(int i=1;i<=n;i++)
//  {
//      cout<<i<<":"<<endl;
//      cout<<"     fa:"<<f[i][0]<<endl;
//      cout<<"     deep:"<<dep[i]<<endl;
//      for(int j=0;j<=3;j++)
//      {
//          cout<<d[i].p[j]<<" ";
//      }
//      cout<<endl;
//  }
    while(m--)
    {
        cin>>type>>aa>>bb;
        if(type==0)
        {
            op=aa;//“op” means “operation”，not “the player of OS”
            for(int i=20;i>=0;i--)
            {
                if(bb>=mi[i])
                {
                    op=f[op][i];
                    bb-=mi[i];
                }
            }
        //  cout<<op<<endl;
            ans=0;
            sum=dep[op];
            for(int i=63;i>=0;i--)
            {
                if(d[aa].pos[i]>=sum)
                {
                    if((ans^d[aa].p[i])>ans)
                    {
                        ans=ans^d[aa].p[i];
                    }
                }
            }
            printf("%llu\n",ans);
        }
        else
        {
            cnt++;
            a[cnt]=bb;
            f[cnt][0]=aa;
            add(aa,cnt);
            ins(aa,cnt);
        }
    }
    return 0;
}

//树上区间线性基前缀和

T3：不会