BZOJ 1036

树链剖分&动态树 模板题

传送门

树链剖分解法
动态树解法

树链剖分

  • 深搜时记录每个节点子树大小
  • 搜到底时建新链
  • 回溯时挑最大的子树
  • 把当前节点加到这颗子树的重链中
  • 对当前节点的其他儿子的重链“封顶”
  • 对每条重链建一棵线段树

修改操作就找到节点所属重链在链的线段树中修改

查询操作就每次从当前所在位置蹦到当前所在链的顶端,然后从顶端的$father$继续向上蹦,重复这样的操作直到蹦到根节点


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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
program bzoj_1036;
var path:array[1..30000]of record top,dep,size,tree:longint; end;
s:array[1..30000]of record fa,size,dep,bl,w,rk:longint; end;
seg:array[1..60000]of record lc,rc,l,r,max,sum:longint; end;
l:array[1..60000]of record ed,pre:longint; end;
lst:array[1..30000]of longint;
n,q,i,a,b,tot,pcnt:longint;
c,cc:char;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure link(a,b:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
end;
procedure dfs(t:longint);
var k,mk,maxs,i:longint;
begin
s[t].size:=1;
s[t].bl:=0;
maxs:=0;
k:=lst[t];
while k<>0 do
begin
if l[k].ed<>s[t].fa then
begin
s[l[k].ed].fa:=t;
s[l[k].ed].dep:=s[t].dep+1;
dfs(l[k].ed);
inc(s[t].size,s[l[k].ed].size);
if s[l[k].ed].size>maxs then
begin
maxs:=s[l[k].ed].size;
mk:=l[k].ed;
end;
end;
k:=l[k].pre;
end;
k:=lst[t];
while k<>0 do
begin
if l[k].ed<>s[t].fa then
begin
if l[k].ed=mk then
begin
s[t].bl:=s[l[k].ed].bl;
s[t].rk:=s[l[k].ed].rk+1;
inc(path[s[t].bl].size);
end else
begin
i:=s[l[k].ed].bl;
path[i].top:=l[k].ed;
path[i].dep:=s[l[k].ed].dep;
end;
end;
k:=l[k].pre;
end;
if s[t].bl=0 then
begin
inc(pcnt);
s[t].bl:=pcnt;
path[s[t].bl].size:=1;
s[t].rk:=1;
end;
end;
procedure build(var t:longint;l,r:longint);
var mid:longint;
begin
inc(tot);
t:=tot;
seg[t].l:=l;
seg[t].r:=r;
if l=r then exit;
mid:=(l+r)>>1;
build(seg[t].lc,l,mid);
build(seg[t].rc,mid+1,r);
end;
procedure modify(t,p,d:longint);
var mid:longint;
begin
if seg[t].l=seg[t].r then
begin
seg[t].sum:=d;
seg[t].max:=d;
exit;
end;
mid:=(seg[t].l+seg[t].r)>>1;
if p<=mid then modify(seg[t].lc,p,d) else modify(seg[t].rc,p,d);
seg[t].max:=max(seg[seg[t].lc].max,seg[seg[t].rc].max);
seg[t].sum:=seg[seg[t].lc].sum+seg[seg[t].rc].sum;
end;
function query(t,l,r:longint;flag:boolean):longint;
var mid,a1,a2:longint;
begin
if (l<=seg[t].l)and(r>=seg[t].r) then
if flag then exit(seg[t].sum) else exit(seg[t].max);
mid:=(seg[t].l+seg[t].r)>>1;
if flag then a1:=0 else a1:=-maxlongint;
a2:=a1;
if l<=mid then a1:=query(seg[t].lc,l,r,flag);
if r>mid then a2:=query(seg[t].rc,l,r,flag);
if flag then exit(a1+a2) else exit(max(a1,a2));
end;
procedure ask(a,b:longint;flag:boolean);
var ans,p,t:longint;
begin
if flag then ans:=0 else ans:=-maxlongint;
while s[a].bl<>s[b].bl do
begin
if path[s[a].bl].dep<path[s[b].bl].dep then
begin
p:=a;
a:=b;
b:=p;
end;
t:=query(path[s[a].bl].tree,s[a].rk,path[s[a].bl].size,flag);
if flag then inc(ans,t) else ans:=max(ans,t);
a:=s[path[s[a].bl].top].fa;
end;
if s[a].rk>s[b].rk then
begin
p:=a;
a:=b;
b:=p;
end;
t:=query(path[s[a].bl].tree,s[a].rk,s[b].rk,flag);
if flag then inc(ans,t) else ans:=max(ans,t);
writeln(ans);
end;
begin
readln(n);
tot:=0;
for i:=1 to n-1 do
begin
readln(a,b);
link(a,b);
link(b,a);
end;
for i:=1 to n do read(s[i].w);
pcnt:=0;
s[1].dep:=1;
s[1].fa:=0;
dfs(1);
path[s[1].bl].top:=1;
path[s[1].bl].dep:=1;
tot:=0;
for i:=1 to pcnt do build(path[i].tree,1,path[i].size);
for i:=1 to n do modify(path[s[i].bl].tree,s[i].rk,s[i].w);
readln(q);
for q:=1 to q do
begin
read(c);
if c='C' then
begin
for i:=1 to 5 do read(cc);
readln(a,b);
modify(path[s[a].bl].tree,s[a].rk,b);
end else
begin
for i:=1 to 3 do read(cc);
readln(a,b);
if cc='X' then ask(a,b,false) else ask(a,b,true);
end;
end;
end.

LCT

动态树嘛…这个姿势只有深刻脑补才能明白…反正我是讲不明白…

直接扔代码跑了算了


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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
program bzoj_1036;
var s:array[0..30000]of record fa,lc,rc,key,max,sum:longint; root,rev:boolean; end;
n,i,j,a,b,q,tot:longint;
ch,c:char;
l:array[1..60000]of record ed,pre:longint; end;
lst:array[1..30000]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure link(a,b:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
end;
procedure dfs(p:longint);
var t:longint;
begin
t:=lst[p];
while t<>0 do
begin
if l[t].ed<>s[p].fa then
begin
s[l[t].ed].fa:=p;
dfs(l[t].ed);
end;
t:=l[t].pre;
end;
end;
procedure pushdown(t:longint);
var p:longint;
begin
if s[t].rev then
begin
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;
s[t].rev:=not s[t].rev;
p:=s[t].lc;
s[t].lc:=s[t].rc;
s[t].rc:=p;
end;
end;
procedure update(t:longint);
begin
if s[t].rev then pushdown(t);
s[t].max:=max(s[t].key,max(s[s[t].lc].max,s[s[t].rc].max));
s[t].sum:=s[s[t].lc].sum+s[s[t].rc].sum+s[t].key;
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 s[p].fa<>0 then
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].lc:=p;
s[p].fa:=t;
s[t].root:=s[p].root;
s[p].root:=false;
update(p);
update(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 s[p].fa<>0 then
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].rc:=p;
s[p].fa:=t;
s[t].root:=s[p].root;
s[p].root:=false;
update(p);
update(t);
end;
procedure splay(t:longint);
begin
while not s[t].root do
begin
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);
update(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;
update(p);
splay(p);
if s[p].rc<>0 then s[s[p].rc].root:=true;
s[p].rc:=t;
s[t].root:=false;
l_rotate(t);
end;
end;
procedure evert(t:longint);
begin
access(t);
s[t].rev:=true;
pushdown(t);
end;
procedure change(t,d:longint);
begin
access(t);
s[t].key:=d;
update(t);
end;
function qsum(a,b:longint):longint;
begin
evert(a);
access(b);
update(b);
exit(s[b].sum);
end;
function qmax(a,b:longint):longint;
begin
evert(a);
access(b);
update(b);
exit(s[b].max);
end;
begin
s[0].max:=-(maxlongint>>1);
readln(n);
for i:=1 to n do s[i].root:=true;
tot:=0;
for i:=1 to n-1 do
begin
readln(a,b);
link(a,b);
link(b,a);
end;
s[1].fa:=0;
dfs(1);
for i:=1 to n do read(s[i].key);
readln(q);
for i:=1 to q do
begin
read(ch);read(ch);
case ch of
'H':begin
for j:=1 to 4 do read(c);
readln(a,b);
change(a,b);
end;
'M':begin
read(c);read(c);
readln(a,b);
writeln(qmax(a,b));
end;
'S':begin
read(c);read(c);
readln(a,b);
writeln(qsum(a,b));
end;
end;
end;
end.