引用毛啸同学的题解：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int N=300010; 7 int fa[N],ch[N][2],key[N]; 8 int tot[N],sum[N],flip[N]; 9 int x[N],y[N],v[N],cnt;10 int t,n,Q,op;11 bool rt(int x){
   return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}12 void Push_up(int x){sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^key[x]^tot[x];}13 void Flip(int x){swap(ch[x][0],ch[x][1]);flip[x]^=1;}14 void Push_down(int x){
   if(flip[x])Flip(ch[x][0]),Flip(ch[x][1]);flip[x]=0;}15 void Rotate(int x){16     int y=fa[x],g=fa[y],c=ch[y][1]==x,r=rt(y);17     ch[y][c]=ch[x][c^1];ch[x][c^1]=y;18     fa[ch[y][c]]=y;fa[y]=x;fa[x]=g;19     if(!r)ch[g][ch[g][1]==y]=x;20     Push_up(y);Push_up(x);21 }22 void P(int x){
   if(!rt(x))P(fa[x]);Push_down(x);}23 void Splay(int x){24     P(x);25     for(int y=fa[x];!rt(x);Rotate(x),y=fa[x])26         if(!rt(y))Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);27     Push_up(x);    28 }29 30 void Access(int x){
   int y=0;31     while(x){Splay(x);32         tot[x]^=sum[y]^sum[ch[x][1]];33         ch[x][1]=y;Push_up(x);x=fa[y=x];34     }35 }36 37 void Make_RT(int x){38     Access(x);39     Splay(x);40     Flip(x);41 }42 43 void Link(int x,int y){44     Make_RT(x);Access(y);45     Splay(y);fa[x]=y;46     tot[y]^=sum[x];47     Push_up(y);48 }49 50 void Cut(int x,int y){51     Make_RT(x);Access(y);Splay(y);52     ch[y][0]=fa[x]=0;Push_up(y);53 }54 55 void Update(int x,int d){56     Access(x);Splay(x);57     key[x]^=d;Push_up(x);58 }59 60 int Query(int x,int y){61     Make_RT(x);Access(y);Splay(y);62     return tot[y]^key[y];63 }64 65 int a,b,now;66 int main(){67     scanf("%d%d%d",&t,&n,&Q);srand(t*t*t*n*n*n*Q*Q*Q);68     for(int i=1;i