1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
| #include <bits/stdc++.h>
#define pb push_back
using ULL = unsigned long long;
const int N = 1e5 + 100;
int n, m;
ULL sum = 0;
std::mt19937_64 rud(114514);
struct Node_of_S{ int x, y; ULL v; } ;
std::vector<Node_of_S> S;
struct LCT
{
struct Node
{
Node *ch[2], *fa;
ULL v, s, vs;
bool rev;
} tr[N];
const Node _null = (Node){nullptr, nullptr, nullptr, 0, 0, 0, false};
Node *null = (Node*)&_null, *tot = tr;
Node* _new(ULL v = 0)
{
*tot = (Node){null, null, null, v, v, 0, false};
return tot++;
}
void adt(Node *x){ std::swap(x->ch[0], x->ch[1]), x->rev ^= 1; }
void up(Node *x){ x->s = x->ch[0]->s ^ x->ch[1]->s ^ x->v ^ x->vs; }
void dw(Node *x){ if (x->rev) adt(x->ch[0]), adt(x->ch[1]), x->rev = false; }
bool is_rt(Node *x){ return x->fa->ch[0] != x && x->fa->ch[1] != x; }
void rot(Node *x)
{
Node *y = x->fa, *z = y->fa;
int k = y->ch[1] == x;
if (!is_rt(y)) z->ch[z->ch[1] == y] = x;
x->fa = z;
y->ch[k] = x->ch[k ^ 1], x->ch[k ^ 1]->fa = y;
y->fa = x, x->ch[k ^ 1] = y;
up(y), up(x);
}
void splay(Node *x)
{
static Node *stk[N];
int top = 0;
Node *y = x, *z;
stk[++top] = x;
while (!is_rt(y)) stk[++top] = y = y->fa;
while (top) dw(stk[top--]);
while (!is_rt(x))
{
y = x->fa, z = y->fa;
if (!is_rt(y)) (y->ch[1] == x) ^ (z->ch[1] == y) ? rot(x) : rot(y);
rot(x);
}
}
void acs(Node *x)
{
for (Node *y = null; x != null; y = x, x = x->fa)
{
splay(x);
x->vs ^= x->ch[1]->s ^ y->s;
x->ch[1] = y;
up(x);
}
}
void mk_rt(Node *x){ acs(x), splay(x), adt(x); }
Node* f_rt(Node *x)
{
acs(x), splay(x);
while (x->ch[0] != null) dw(x), x = x->ch[0];
return x;
}
void lk(int idx, int idy)
{
Node *x = tr + idx - 1, *y = tr + idy - 1;
mk_rt(x);
if (f_rt(y) == x) return ;
x->fa = y, y->vs ^= x->s;
up(y);
}
void cut(int idx, int idy)
{
Node *x = tr + idx - 1, *y = tr + idy - 1;
mk_rt(x);
if (f_rt(y) != x) return ;
x->fa = y->ch[0] = null;
up(y);
}
void cg(int idx, ULL v)
{
Node *x = tr + idx - 1;
acs(x), splay(x), x->v ^= v;
up(x);
}
ULL ask(int idx, int idy)
{
Node *x = tr + idx - 1, *y = tr + idy - 1;
mk_rt(x), acs(y), splay(y);
return x->s;
}
} lct;
int main()
{
int id;
scanf("%d %d %d", &id, &n, &m);
for (int i = 1; i <= n; ++i) lct._new();
for (int i = 1, u, v; i < n; ++i)
{
scanf("%d %d", &u, &v);
lct.lk(u, v);
}
while (m--)
{
int op, x, y, u, v;
scanf("%d %d", &op, &x);
if (op == 1)
{
scanf("%d %d %d", &y, &u, &v);
lct.cut(x, y), lct.lk(u, v);
}
else if (op == 2)
{
scanf("%d", &y);
ULL t = rud();
lct.cg(x, t), lct.cg(y, t);
S.pb({x, y, t}), sum ^= t;
}
else if (op == 3)
{
auto t = S[x - 1];
lct.cg(t.x, t.v), lct.cg(t.y, t.v);
sum ^= t.v;
}
else
{
scanf("%d", &y);
puts(lct.ask(x, y) == sum ? "YES" : "NO");
}
}
return 0;
}
|