Article From:https://www.cnblogs.com/MikuKnight/p/9064675.html

A very good blog

Write down a few points that you’ve been stuck with before:

1.accessInstead of finding a path to the real root, the root of the top splay can be found (makeroot).

2.findrootFind the root of the original tree in X (the smallest depth) and rotate to the root of the current splay.

tips:Do not understand specifically, do more questions

```#include<cstdio>
#include<cctype>
#include<algorithm>
#define ls tr[x][0]
#define rs tr[x][1]
#define maxn 300002
using namespace std;
int n,m,res[maxn],tr[maxn][2],rev[maxn],w[maxn],tmp[maxn],f[maxn];
inline void pushup(int x){res[x]=res[ls]^res[rs]^w[x];}
inline void pushr(int x){swap(ls,rs);rev[x]^=1;}
inline void pushdown(int x){if(rev[x]){if(ls)pushr(ls);if(rs)pushr(rs);rev[x]=0;}}
char ch=getchar();x=0;int f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
x*=f;
}
inline bool isroot(int x){return (tr[f[x]][0]==x||tr[f[x]][1]==x);}
inline void rotate(int x){
int fa=f[x],gfa=f[fa],whicx=tr[fa][1]==x,flag=isroot(fa);//Note that flag should be assigned first, because after that the father will become X.
tr[fa][whicx]=tr[x][whicx^1];if(tr[fa][whicx])f[tr[fa][whicx]]=fa;
tr[x][whicx^1]=fa;f[fa]=x;
f[x]=gfa;
if(flag)tr[gfa][tr[gfa][1]==fa]=x;
pushup(fa);
}
inline void splay(int x){
int y=x,siz=0,z;
tmp[++siz]=y;
while(isroot(y))tmp[++siz]=y=f[y];
while(siz)pushdown(tmp[siz--]);
while(isroot(x)){
y=f[x];z=f[y];
if(isroot(y))rotate((tr[y][1]==x)==(tr[z][1]==y)?y:x);
rotate(x);
}
pushup(x);
}
inline void access(int x){
for(int y=0;x;x=f[y=x])splay(x),rs=y,pushup(x);
}
inline void makeroot(int x){access(x);splay(x);pushr(x);}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}
inline int findroot(int x){
access(x);splay(x);
while(ls)pushdown(x),x=ls;
return x;
}
inline void cut(int x,int y){
makeroot(x);if(findroot(y)==x&&f[x]==y&&!rs){f[x]=tr[y][0]=0;pushup(y);}
}
int main(){
int typ,x,y;
while(m--){
switch(typ){
case 0:split(x,y);printf("%d\n",res[y]);break;