findroot代码如下

int findroot(int x) { 
   access(x); 
   /*splay(x);*/ 
   while (lc) pushdown(x), x=lc; 
   splay(x);    
   return x; 
}

90分代码如下

#include <bits/stdc++.h>
#define lc ch[x][0]
#define rc ch[x][1]
using namespace std;
const int N=800005;
int ch[N][2], v[N], s[N], r[N], f[N], st[N];

bool nroot(int x) { return ch[f[x]][0]==x||ch[f[x]][1]==x; }
void pushr(int x) { if (x) swap(lc, rc), r[x]^=1; }
void pushdown(int x) { if (r[x]) {r[x]=0, pushr(lc), pushr(rc); } }
void update(int x) { if (x) s[x]=v[x]^s[lc]^s[rc]; }
void rotate(int x) { int y=f[x], z=f[y], k=ch[y][1]==x, w=ch[x][!k]; 
    if (nroot(y)) ch[z][ch[z][1]==y]=x; ch[y][k]=w, ch[x][!k]=y;
    if(w) f[w]=y; f[y]=x; f[x]=z; update(y); }
void splay(int x) { 
	int t=0, y=x; while (nroot(y)) st[t++]=y, y=f[y]; st[t++]=y; 
	for (int i=t-1; i>=0; i--) pushdown(st[i]);
    while (nroot(x)) { 
        int y=f[x], z=f[y]; 
        if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y); 
        rotate(x);
    } 
    update(x); 
}
void access(int x) { for (int y=0; x; x=f[y=x]) splay(x), rc=y, update(x); }
void makeroot(int x) { access(x), splay(x), pushr(x); }
int findroot(int x) { access(x); /*splay(x);*/ while (lc) pushdown(x), x=lc; splay(x); return x; }
void link(int x, int y) { makeroot(x); if (findroot(y)!=x) f[x]=y; }
void cut(int x, int y) { makeroot(x); if (findroot(y)==x&&f[y]==x&&ch[y][0]==0) ch[x][1]=f[y]=0; update(x); }
void split(int x, int y) { makeroot(x); access(y); splay(y); }

int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) scanf("%d", &v[i]);
    while (m--) {
        int op, x, y; scanf("%d%d%d", &op, &x, &y);
        if (op==0) split(x, y), printf("%d\n", s[y]);
        if (op==1) link(x, y);
        if (op==2) cut(x, y);
        if (op==3) splay(x), v[x]=y;
    }
    return 0;
}