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
| struct Node
{
int p, s[2], tag, v;
} tr[N];
void pushup (int x) { }
void reverse (int x) { tr[x].tag ^= 1; swap(tr[x].s[0], tr[x].s[1]); }
void pushdown (int x)
{
if (!tr[x].tag) return;
reverse(tr[x].s[0]), reverse(tr[x].s[1]);
tr[x].tag = 0;
}
bool isrt (int x) { return tr[tr[x].p].s[0] ^ x && tr[tr[x].p].s[1] ^ x; }
void rotate (int x)
{
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
if (!isrt(y)) tr[z].s[tr[z].s[1] == y] = x;
tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);
}
void update (int x)
{
if (!isrt(x)) update(tr[x].p);
pushdown(x);
}
void splay (int x)
{
update(x);
for (; !isrt(x); rotate(x))
{
int y = tr[x].p, z = tr[y].p;
if (!isrt(y)) rotate((y == tr[z].s[1]) ^ (x == tr[y].s[1]) ? x : y);
}
}
void access (int t)
{
for (int x = t, y = 0; x; y = x, x = tr[x].p)
splay(x), tr[x].s[1] = y, pushup(x);
splay(t);
}
void mkrt (int x) { access(x); reverse(x); }
int findrt (int x)
{
access(x);
for (; tr[x].s[0]; x = tr[x].s[0]) pushdown(x);
splay(x);
return x;
}
void link (int x, int y) { mkrt(x); if (findrt(y) ^ x) tr[x].p = y; }
void cut (int x, int y)
{
mkrt(x);
if (findrt(y) == x && tr[y].p == x && !tr[y].s[0])
{
tr[y].p = tr[x].s[1] = 0;
pushup(x);
}
}
|