BZOJ 2049

动态树模板题

传送门

全都是动态树的基础操作…就不讲了吧…看代码脑补得了….实际是不会讲啊QAQ


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
program bzoj_2049;
var s:array[0..10000]of record fa,lc,rc:longint; root,rev:boolean; end;
n,m,i,j,a,b:longint;
c,cc:char;
procedure pushdown(t:longint);
var p:longint;
begin
if not s[t].rev then exit;
p:=s[t].lc;
s[t].lc:=s[t].rc;
s[t].rc:=p;
s[t].rev:=not s[t].rev;
if s[t].lc<>0 then s[s[t].lc].rev:=not s[s[t].lc].rev;
if s[t].rc<>0 then s[s[t].rc].rev:=not s[s[t].rc].rev;
end;
procedure l_rotate(t:longint);
var p:longint;
begin
p:=s[t].fa;
s[p].rc:=s[t].lc;
if s[t].lc<>0 then s[s[t].lc].fa:=p;
s[t].fa:=s[p].fa;
if p=s[s[p].fa].lc then s[s[p].fa].lc:=t;
if p=s[s[p].fa].rc then s[s[p].fa].rc:=t;
s[t].root:=s[p].root;
s[p].root:=false;
s[t].lc:=p;
s[p].fa:=t;
end;
procedure r_rotate(t:longint);
var p:longint;
begin
p:=s[t].fa;
s[p].lc:=s[t].rc;
if s[t].rc<>0 then s[s[t].rc].fa:=p;
s[t].fa:=s[p].fa;
if p=s[s[p].fa].lc then s[s[p].fa].lc:=t;
if p=s[s[p].fa].rc then s[s[p].fa].rc:=t;
s[t].root:=s[p].root;
s[p].root:=false;
s[t].rc:=p;
s[p].fa:=t;
end;
procedure splay(t:longint);
begin
while not s[t].root do
begin
if s[s[t].fa].rev then pushdown(s[t].fa);
if s[s[s[t].fa].lc].rev then pushdown(s[s[t].fa].lc);
if s[s[s[t].fa].rc].rev then pushdown(s[s[t].fa].rc);
if t=s[s[t].fa].lc then r_rotate(t) else l_rotate(t);
end;
end;
procedure access(t:longint);
var p:longint;
begin
splay(t);
if s[t].rev then pushdown(t);
if s[t].rc<>0 then s[s[t].rc].root:=true;
s[t].rc:=0;
while s[t].fa<>0 do
begin
p:=s[t].fa;
splay(p);
if s[p].rev then pushdown(p);
if s[p].rc<>0 then s[s[p].rc].root:=true;
s[t].root:=false;
s[p].rc:=t;
s[t].fa:=p;
splay(t);
end;
end;
procedure evert(t:longint);
begin
access(t);
s[t].rev:=true;
pushdown(t);
end;
procedure link(a,b:longint);
begin
evert(a);
access(b);
s[a].lc:=b;
s[b].fa:=a;
s[b].root:=false;
end;
procedure cut(a,b:longint);
begin
evert(a);
access(b);
if s[b].lc<>0 then s[s[b].lc].root:=true;
s[a].fa:=0;
s[b].lc:=0;
end;
function find(t:longint):longint;
begin
access(t);
while s[t].lc<>0 do t:=s[t].lc;
exit(t);
end;
begin
readln(n,m);
fillchar(s,sizeof(s),0);
for i:=1 to n do s[i].root:=true;
for i:=1 to m do
begin
read(c);
case c of
'C':begin
for j:=1 to 6 do read(cc);
readln(a,b);
link(a,b);
end;
'D':begin
for j:=1 to 6 do read(cc);
readln(a,b);
cut(a,b);
end;
'Q':begin
for j:=1 to 4 do read(cc);
readln(a,b);
if find(a)=find(b) then writeln('Yes') else writeln('No');
end;
end;
end;
end.