3282: Tree
Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 1714 Solved: 765
[Submit][Status][Discuss]
Description
给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。
Input
第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。
第２行到第Ｎ＋１行，每行一个整数，整数在［１，１０＾９］内，代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。
Output
对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。
Sample Input
3 3
1
2
3
1 1 2
0 1 2
0 1 1
1
2
3
1 1 2
0 1 2
0 1 1
Sample Output
3
1
1
HINT
１＜＝Ｎ，Ｍ＜＝３０００００
Source
莫名其妙的红色，LCT模板题
#include <bits/stdc++.h>
inline int nextChar(void) {
static const int siz = 1 << 20;
static char buffer[siz];
static char *head = buffer + siz;
static char *tail = buffer + siz;
if (head == tail)fread(head = buffer, 1, siz, stdin);
return int(*head++);
}
inline int nextInt(void) {
register int ret = 0;
register int neg = false;
register int bit = nextChar();
for (; bit < 48; bit = nextChar())
if (bit == '-')neg ^= true;
for (; bit > 47; bit = nextChar())
ret = ret * 10 + bit - '0';
return neg ? -ret : ret;
}
const int mxn = 300005;
int n, m, top;
int stk[mxn];
int val[mxn];
int sum[mxn];
int fat[mxn];
int rev[mxn];
int son[mxn][2];
inline bool isroot(int t) {
int f = fat[t];
if (!f)return true;
if (son[f][0] == t)return false;
if (son[f][1] == t)return false;
return true;
}
inline void update(int t) {
sum[t] = val[t];
if (son[t][0])sum[t] ^= sum[son[t][0]];
if (son[t][1])sum[t] ^= sum[son[t][1]];
}
inline void push(int t) {
rev[t] = 0;
std::swap(son[t][0], son[t][1]);
if (son[t][0])rev[son[t][0]] ^= 1;
if (son[t][1])rev[son[t][1]] ^= 1;
}
inline void pushdown(int t) {
for (stk[++top] = t; t; )
stk[++top] = t = fat[t];
for (; top; --top)
if (rev[stk[top]])
push(stk[top]);
}
inline void connect(int t, int f, int k) {
if (t)fat[t] = f;
if (f)son[f][k] = t;
}
inline void rotate(int t) {
int f = fat[t];
int g = fat[f];
int s = son[f][1] == t;
connect(son[t][!s], f, s);
connect(f, t, !s);
fat[t] = g;
if (g && son[g][0] == f)son[g][0] = t;
if (g && son[g][1] == f)son[g][1] = t;
update(f);
update(t);
}
inline void splay(int t) {
pushdown(t);
while (!isroot(t)) {
int f = fat[t];
int g = fat[f];
if (isroot(f))
rotate(t);
else {
int a = f && son[f][1] == t;
int b = g && son[g][1] == f;
if (a == b)
rotate(f), rotate(t);
else
rotate(t), rotate(t);
}
}
}
inline void access(int t) {
for (int p = 0; t; p = t, t = fat[t])
splay(t), son[t][1] = p, update(t);
}
inline void makeroot(int t) {
access(t), splay(t), rev[t] ^= 1;
}
inline void cut(int a, int b) {
makeroot(a), access(b), splay(b);
if (son[b][0] == a)son[b][0] = fat[a] = 0;
}
inline void link(int t, int f) {
makeroot(t), fat[t] = f;
}
inline int find(int t) {
access(t), splay(t);
while (son[t][0])
t = son[t][0];
return t;
}
signed main(void) {
n = nextInt();
m = nextInt();
for (int i = 1; i <= n; ++i)
val[i] = sum[i] = nextInt();
for (int i = 1; i <= m; ++i) {
int k = nextInt();
int x = nextInt();
int y = nextInt();
switch (k) {
case 0 :
makeroot(x);
access(y);
splay(y);
printf("%d
", sum[y]);
break;
case 1:
if (find(x) != find(y))
link(x, y);
break;
case 2:
if (find(x) == find(y))
cut(x, y);
break;
case 3:
access(x);
splay(x);
val[x] = y;
update(x);
break;
}
}
}
@Author: YouSiki