3282: Tree
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
#include <cstdio>
#include <algorithm>
using namespace std;
const int MaxN = 300010;
int N, M;
struct point {
int l, r, fa, key, rev, xors;
point (int a = 0, int b = 0, int f = 0, int x = 0, int r = 0, int s = 0) {
l = a, r = b, fa = f, key = x, rev = r, xors = s;
}
#define l(x) (p[x].l)
#define r(x) (p[x].r)
#define fa(x) (p[x].fa)
#define key(x) (p[x].key)
#define rev(x) (p[x].rev)
#define xors(x) (p[x].xors)
}p[MaxN];
int que[MaxN], qr;
void Rev(int x) {
rev(x) ^= 1;
swap(l(x), r(x));
}
void Down(int x) {
if (rev(x)) {
if (l(x)) Rev(l(x));
if (r(x)) Rev(r(x));
rev(x) = 0;
}
}
void Up(int x) {
xors(x) = key(x) ^ (l(x) ? xors(l(x)) : 0) ^ (r(x) ? xors(r(x)) : 0);
}
bool isRoot(int x) {
return !fa(x) || l(fa(x)) != x && r(fa(x)) != x;
}
bool which(int x) {
return r(fa(x)) == x;
}
void Turn(int x) {
int y = fa(x), z = fa(y), w = l(y) == x ? r(x) : l(x);
fa(x) = z; if (!isRoot(y)) (l(z) == y ? l(z) : r(z)) = x;
fa(y) = x; (l(y) == x ? r(x) : l(x)) = y;
if (w) fa(w) = y; (l(y) == x ? l(y) : r(y)) = w;
Up(y), Up(x);
}
void Splay(int x) {
que[qr = 0] = x;
for (int y = x; !isRoot(y); y = fa(y)) que[++qr] = fa(y);
for (; qr >= 0; --qr) Down(que[qr]);
while (!isRoot(x)) {
if (!isRoot(fa(x)))
if (which(fa(x)) == which(x)) Turn(fa(x));
else Turn(x);
Turn(x);
}
}
void access(int x) {
for (int y = 0; x; y = x, x = fa(x))
Splay(x), r(x) = y, Up(x);
}
void MakeRoot(int x) {
access(x), Splay(x);
Rev(x);
}
int findRoot(int x) {
access(x), Splay(x);
que[qr = 0] = x;
while (Down(x), l(x)) que[++qr] = x = l(x);
for (; qr >= 0; --qr) Up(que[qr]);
return x;
}
void Connect(int x, int y) {
if (findRoot(x) == findRoot(y)) return;
MakeRoot(x);
fa(x) = y;
}
void Delete(int x, int y) {
if (findRoot(x) != findRoot(y)) return;
MakeRoot(x), access(y), Splay(y);
l(y) = fa(x) = 0; Up(y);
}
void Change(int x, int key) {
MakeRoot(x);
key(x) = key;
Up(x);
}
int Query(int x, int y) {
MakeRoot(x), access(y), Splay(y);
return xors(y);
}
int Get() {
char Ch;
while ((Ch = getchar()) < '0' || Ch > '9');
int Num = Ch - '0';
while ((Ch = getchar()) >= '0' && Ch <= '9')
Num = Num * 10 + Ch - '0';
return Num;
}
int main()
{
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i)
key(i) = xors(i) = Get();
for (int i = 1; i <= M; ++i) {
int opt = Get(), x = Get(), y = Get();
if (opt == 0)
printf("%d\n", Query(x, y));
else
if (opt == 1)
Connect(x, y);
else
if (opt == 2)
Delete(x, y);
else
Change(x, y);
}
}
评论 (0)
