BZOJ

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.