rt
#include <bits/stdc++.h>
using namespace std;
#define re register
namespace IO {
inline char ch() {
static char buf[1 << 21], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
? EOF
: *p1++;
}
inline int in() {
int s = 0, f = 1;
char x;
for (x = getchar(); x < '0' || x > '9'; x = getchar())
if (x == '-') f = -1;
for (; x >= '0' && x <= '9'; x = getchar()) s = (s * 10) + (x & 15);
return f == 1 ? s : -s;
}
} // namespace IO
using namespace IO;
const int A = 3e5 + 5;
int n, m;
struct LCT {
int ch[2], f, rev;
int val, sum;
} tr[A];
#define ls(x) tr[x].ch[0]
#define rs(x) tr[x].ch[1]
inline int isroot(int x) { return !(ls(tr[x].f) == x || rs(tr[x].f) == x); }
inline void pushup(int x) {
tr[x].sum = tr[ls(x)].sum ^ tr[rs(x)].sum ^ tr[x].val;
return;
}
inline void reverse(int x) {
if (x) {
swap(ls(x), rs(x));
tr[x].rev ^= 1;
}
return;
}
inline void pushdown(int x) {
if (tr[x].rev) {
reverse(ls(x)), reverse(rs(x));
tr[x].rev ^= 1;
}
return;
}
inline void rotate(int x) {
int y = tr[x].f, z = tr[y].f;
int k = (rs(y) == x);
if (!isroot(y)) tr[z].ch[rs(z) == y] = x;
tr[x].f = z, tr[y].ch[k] = tr[x].ch[k ^ 1];
tr[tr[x].ch[k ^ 1]].f = y;
tr[x].ch[k ^ 1] = y, tr[y].f = x;
pushup(x), pushup(y);
return;
}
int st[A],top;
inline void pushpath(int x) {
top=0;
st[++top] = x;
for (int i = x; !isroot(i); i = tr[i].f) st[++top] = tr[i].f;
for (int i = top; i; i--) pushdown(st[i]);
return;
}
inline void splay(int x) {
pushpath(x);
while (!isroot(x)) {
int y = tr[x].f, z = tr[y].f;
if (!isroot(y)) {
if ((rs(y) == x) == (rs(z) == y))
rotate(y);
else
rotate(x);
}
rotate(x);
}
pushup(x);
return;
}
inline void access(int x) {
for (int y = 0; x; y = x, x = tr[x].f) splay(x), rs(x) = y, pushup(x);
return;
}
inline int findroot(int x) {
access(x), splay(x);
while (ls(x)) pushdown(x), x = ls(x);
// splay(x); //
return x;
}
inline void makeroot(int x) {
access(x), splay(x), reverse(x);
return;
}
inline void split(int x, int y) {
makeroot(x), access(y), splay(y);
return;
}
inline void link(int x, int y) {
makeroot(x);
if (findroot(y) != x) tr[x].f = y;
return;
}
inline void cut(int x, int y) {
makeroot(x);
if (findroot(y) == x && tr[x].f == y && ls(y) == x) tr[x].f = 0, ls(y) = 0;
return;
} //
signed main() {
n = in(), m = in();
for (int i = 1; i <= n; i++) tr[i].val = in();
while (m--) {
int opt = in();
if (opt == 0) {
int u = in(), v = in();
split(u, v);
printf("%d\n", tr[v].sum);
} else if (opt == 1) {
int u = in(), v = in();
link(u, v);
} else if (opt == 2) {
int u = in(), v = in();
cut(u, v);
} else {
int u = in(), v = in();
splay(u);
tr[u].val = v;
}
}
return 0;
}
就是这句
inline int findroot(int x) {
access(x), splay(x);
while (ls(x)) pushdown(x), x = ls(x);
// splay(x); //
return x;
}
去掉注释就wa了。。。