概念
樹剖就是将一棵樹暴力拆成幾條鍊，然後對于這樣一個序列，我們就可以套上資瓷區間處理的一些東西qwq（比如說線段樹，樹狀數組
可以解決的問題：
- 将樹從$x$到$y$結點最短路徑上所有節點的值都加上$z$
- 求樹從$x$到$y$結點最短路徑上所有節點的值之和/最大值
- 将以$x$為根節點的子樹内所有節點值都加上$z$
- 求以$x$為根節點的子樹内所有節點值之和/最大值
一些概念：
- 重兒子：父親節點的所有兒子中子樹結點數目最多（$size$最大）的結點；
- 輕兒子：父親節點中除了重兒子以外的兒子；
- 重邊：父親結點和重兒子連成的邊；
- 輕邊：父親節點和輕兒子連成的邊；
- 重鍊：由多條重邊連接配接而成的路徑；
- 輕鍊：由多條輕邊連接配接而成的路徑；
實作
一些定義：
- $f(x)$表示節點$x$在樹上的父親
- $dep(x)$表示節點$x$在樹上的深度
- $siz(x)$表示節點$x$的子樹的節點的個數
- $son(x)$表示節點$x$的重兒子
- $top(x)$表示節點$s$所在重鍊的頂部節點（深度最小）
- $id(x)$表示節點$x$線上段樹中的編号
- $rk(x)$表示線段樹中标号為$x$的節點對應的樹上節點的編号
1、第一次DFS，對于一個點求出它所在的子樹的大小、它的重兒子，順便記錄其父節點和深度。
1 void dfs1(int u, int fa, int depth) //目前節點、父節點、層次深度
2 {
3 //printf("u:%d fa:%d depth:%d\n", u, fa, depth);
4 f[u] = fa;
5 deep[u] = depth;
6 size[u] = 1; //這個點本身的size
7 for(int i = head[u];i;i = edges[i].next)
8 {
9 int v = edges[i].to;
10 if(v == fa) continue;
11 dfs1(v, u, depth+1);
12 size[u] += size[v]; //子節點的size已被處理，用它來更新父節點的size
13 if(size[v] > size[son[u]]) son[u] = v; //選取size最大的作為重兒子
14 }
15 } 2、第二次DFS，連接配接重鍊，同時标記每個節點的DFS序。為了用資料結構來維護重鍊，我們在DFS時保證一條重鍊上的節點DFS序連續。一個節點的子樹内DFS序也連續。
1 void dfs2(int u, int t) //目前節點、重鍊頂端
2 {
3 printf("u:%d t:%d\n", u, t);
4 top[u] = t;
5 id[u] = ++cnt; //标記dfs序
6 rk[cnt] = u; //序号cnt對應節點u
7 if(!son[u]) return; //沒有兒子？
8 dfs2(son[u], t); //我們選擇優先進入重兒子來保證一條重鍊上各個節點dfs序連續
9
10 for(int i = head[u];i;i = edges[i].next)
11 {
12 int v = edges[i].to;
13 if(v != son[u] && v != f[u]) dfs2(v, v); //這個點位于輕鍊頂端，那麼它的top必然為它本身
14 }
15 } 3、兩遍DFS就是樹鍊剖分的主要處理，通過dfs我們已經保證一條重鍊上各個節點的dfs序連續，那麼可以想到，我們可以通過資料結構來維護（以線段樹為例）來維護一條重鍊的資訊。
維護和
1 ll querysum(int x, int y)
2 {
3 int fx = top[x], fy = top[y];
4 ll ans = 0;
5 while(fx != fy) //當兩者不在同一條重鍊上
6 {
7 if(deep[fx] >= deep[fy])
8 {
9 ans += st.query2(1, 1, n, 0, id[fx], id[x]); //線段樹區間求和，計算這條重鍊的貢獻
10 x = f[fx]; fx = top[x];
11 }
12 else
13 {
14 ans += st.query2(1, 1, n, 0, id[fy], id[y]);
15 y = f[fy]; fy = top[y];
16 }
17 }
18
19 //循環結束，兩點位于同一重鍊上，但兩者不一定為同一點，是以還要加上這兩點之間的貢獻
20 if(id[x] <= id[y])
21 {
22 ans += st.query2(1, 1, n, 0, id[x], id[y]);
23 }
24 else
25 {
26 ans += st.query2(1, 1, n, 0, id[y], id[x]);
27 }
28 return ans;
29 } 維護最大值
1 ll querymax(int x, int y)
2 {
3 int fx = top[x], fy = top[y];
4 ll ans = -INF;
5 while(fx != fy) //當兩者不在同一條重鍊上
6 {
7 if(deep[fx] >= deep[fy])
8 {
9 ans = max(ans, st.query1(1, 1, n, 0, id[fx], id[x])); //線段樹區間求和，計算這條重鍊的貢獻
10 x = f[fx]; fx = top[x];
11 }
12 else
13 {
14 ans = max(ans, st.query1(1, 1, n, 0, id[fy], id[y]));
15 y = f[fy]; fy = top[y];
16 }
17 }
18 //循環結束，兩點位于同一重鍊上，但兩者不一定為同一點，是以還要加上這兩點之間的貢獻
19 if(id[x] <= id[y]) ans = max(ans, st.query1(1, 1, n, 0, id[x], id[y]));
20 else ans = max(ans, st.query1(1, 1, n, 0, id[y], id[x]));
21 return ans;
22 } 時間複雜度
對于每次詢問，最多經過$O(log\ n)$條重鍊，每條重鍊上線段樹的複雜度為$O(log \ n)$，此時總的時間複雜度為$O(nlogn+q{log}^2n)$。實際上重鍊個數很難達到$O(log \ n)$（可以用完全二叉樹卡滿），是以樹剖在一般情況下常數較小。
完整的代碼
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 typedef long long ll;
5 #define lc o <<1
6 #define rc o <<1 | 1
7 const int INF = 0x3f3f3f3f;
8 const int maxn = 100000 + 10;
9 struct Edge
10 {
11 int to, next;
12 }edges[2*maxn];
13 int head[maxn];
14 int cur, f[maxn], deep[maxn], size[maxn], son[maxn], rk[maxn], id[maxn], top[maxn], cnt;
15 int n, root, qcnt, w[maxn];
16
17 inline void addedge(int u, int v)
18 {
19 ++cur;
20 edges[cur].next = head[u];
21 head[u] = cur;
22 edges[cur].to = v;
23 }
24
25 struct SegTree{
26 ll sum[maxn << 2], maxv[maxn << 2], addv[maxn << 2];
27 void build(int o, int l, int r)
28 {
29 if(l == r)
30 {
31 sum[o] = maxv[o] = w[rk[l]];
32 }
33 else
34 {
35 int mid = (l + r) >> 1;
36 build(lc, l, mid);
37 build(rc, mid+1, r);
38 sum[o] = sum[lc] + sum[rc];
39 maxv[o] = max(maxv[lc], maxv[rc]);
40 }
41 }
42
43 void maintain(int o, int l, int r)
44 {
45 if(l == r) //如果是葉子結點
46 {
47 maxv[o] = w[rk[l]];
48 sum[o] = w[rk[l]];
49 }
50 else //如果是非葉子結點
51 {
52 maxv[o] = max(maxv[lc], maxv[rc]);
53 sum[o] = sum[lc] + sum[rc];
54 }
55 maxv[o] += addv[o]; //考慮add操作
56 sum[o] += addv[o] * (r-l+1);
57 }
58 //區間修改，[cl,cr] += v;
59 void update(int o, int l, int r, int cl, int cr, int v) //
60 {
61 //printf("o:%d l:%d r:%d\n", o, l, r);
62 if(cl <= l && r <= cr) addv[o] += v;
63 else
64 {
65 int m = l + (r-l) /2;
66 if(cl <= m) update(lc, l, m, cl, cr, v);
67 if(cr > m) update(rc, m+1, r, cl, cr, v);
68 }
69 maintain(o, l, r);
70 }
71
72 //區間查詢1,max{ql,qr}
73 ll query1(int o, int l,int r, int add, int ql, int qr)
74 {
75 //prllf("o:%d l:%d r:%d\n", o, l, r);
76 if(ql <= l && r <= qr) return maxv[o] + add;
77 else
78 {
79 int m = l + (r - l) / 2;
80 ll ans = -INF;
81 add += addv[o];
82 if(ql <= m) ans = max(ans, query1(lc, l, m, add, ql, qr));
83 if(qr > m) ans = max(ans, query1(rc, m+1, r, add, ql, qr));
84 return ans;
85 }
86 }
87
88 //區間查詢2,sum{ql,qr}
89 ll query2(int o, int l,int r, int add, int ql, int qr)
90 {
91 //prllf("o:%d l:%d r:%d ql:%d qr:%d\n", o, l, r, ql, qr);
92 if(ql <= l && r <= qr) return sum[o] + add * (r-l+1);
93 else
94 {
95 int m = l + (r - l) / 2;
96 ll ans = 0;
97 add += addv[o];
98 if(ql <= m) ans += query2(lc, l, m, add, ql, qr);
99 if(qr > m) ans += query2(rc, m+1, r, add, ql, qr);
100 return ans;
101 }
102 }
103 }st;
104
105 void dfs1(int u, int fa, int depth) //目前節點、父節點、層次深度
106 {
107 //printf("u:%d fa:%d depth:%d\n", u, fa, depth);
108 f[u] = fa;
109 deep[u] = depth;
110 size[u] = 1; //這個點本身的size
111 for(int i = head[u];i;i = edges[i].next)
112 {
113 int v = edges[i].to;
114 if(v == fa) continue;
115 dfs1(v, u, depth+1);
116 size[u] += size[v]; //子節點的size已被處理，用它來更新父節點的size
117 if(size[v] > size[son[u]]) son[u] = v; //選取size最大的作為重兒子
118 }
119 }
120
121 void dfs2(int u, int t) //目前節點、重鍊頂端
122 {
123 printf("u:%d t:%d\n", u, t);
124 top[u] = t;
125 id[u] = ++cnt; //标記dfs序
126 rk[cnt] = u; //序号cnt對應節點u
127 if(!son[u]) return; //沒有兒子？
128 dfs2(son[u], t); //我們選擇優先進入重兒子來保證一條重鍊上各個節點dfs序連續
129
130 for(int i = head[u];i;i = edges[i].next)
131 {
132 int v = edges[i].to;
133 if(v != son[u] && v != f[u]) dfs2(v, v); //這個點位于輕鍊頂端，那麼它的top必然為它本身
134 }
135 }
136
137 ll querymax(int x, int y)
138 {
139 int fx = top[x], fy = top[y];
140 ll ans = -INF;
141 while(fx != fy) //當兩者不在同一條重鍊上
142 {
143 if(deep[fx] >= deep[fy])
144 {
145 ans = max(ans, st.query1(1, 1, n, 0, id[fx], id[x])); //線段樹區間求和，計算這條重鍊的貢獻
146 x = f[fx]; fx = top[x];
147 }
148 else
149 {
150 ans = max(ans, st.query1(1, 1, n, 0, id[fy], id[y]));
151 y = f[fy]; fy = top[y];
152 }
153 }
154 //循環結束，兩點位于同一重鍊上，但兩者不一定為同一點，是以還要加上這兩點之間的貢獻
155 if(id[x] <= id[y]) ans = max(ans, st.query1(1, 1, n, 0, id[x], id[y]));
156 else ans = max(ans, st.query1(1, 1, n, 0, id[y], id[x]));
157 return ans;
158 }
159
160 /*修改和查詢的原理是一緻的，以查詢操作為例，其實就是個LCA，不過這裡要使用top數組加速，因為top可以直接跳到該重鍊的起始頂點*/
161 /*注意，每次循環隻能跳一次，并且讓結點深的那個跳到top的位置，避免兩者一起跳而插肩而過*/
162 ll querysum(int x, int y)
163 {
164 int fx = top[x], fy = top[y];
165 ll ans = 0;
166 while(fx != fy) //當兩者不在同一條重鍊上
167 {
168 if(deep[fx] >= deep[fy])
169 {
170 ans += st.query2(1, 1, n, 0, id[fx], id[x]); //線段樹區間求和，計算這條重鍊的貢獻
171 x = f[fx]; fx = top[x];
172 }
173 else
174 {
175 ans += st.query2(1, 1, n, 0, id[fy], id[y]);
176 y = f[fy]; fy = top[y];
177 }
178 }
179
180 //循環結束，兩點位于同一重鍊上，但兩者不一定為同一點，是以還要加上這兩點之間的貢獻
181 if(id[x] <= id[y])
182 {
183 ans += st.query2(1, 1, n, 0, id[x], id[y]);
184 }
185 else
186 {
187 ans += st.query2(1, 1, n, 0, id[y], id[x]);
188 }
189 return ans;
190 }
191
192 void update_add(int x, int y, int add)
193 {
194 int fx = top[x], fy = top[y];
195 while(fx != fy) //當兩者不在同一條重鍊上
196 {
197 if(deep[fx] >= deep[fy])
198 {
199 st.update(1, 1, n, id[fx], id[x], add);
200 x = f[fx]; fx = top[x];
201 }
202 else
203 {
204 st.update(1, 1, n, id[fy], id[y], add);
205 y = f[fy]; fy = top[y];
206 }
207 }
208 //循環結束，兩點位于同一重鍊上，但兩者不一定為同一點，是以還要加上這兩點之間的貢獻
209 if(id[x] <= id[y]) st.update(1, 1, n, id[x], id[y], add);
210 else st.update(1, 1, n, id[y], id[x], add);
211 }
212
213 int main()
214 {
215 scanf("%d%d%d", &n, &root, &qcnt);
216 for(int i = 1;i <= n;i++) scanf("%d", &w[i]);
217 for(int i = 1;i < n;i++)
218 {
219 int u, v;
220 scanf("%d%d", &u, &v);
221 addedge(u, v);
222 addedge(v, u);
223 }
224 dfs1(root, -1, 1);
225 dfs2(root, root);
226
227 for(int i = 1;i <= n;i++) printf("%d ", id[i]);
228 printf("\n");
229 for(int i = 1;i <= n;i++) printf("%d ", rk[i]);
230 printf("\n");
231
232 st.build(1, 1, n);
233
234 while(qcnt--)
235 {
236 int op;
237 scanf("%d", &op);
238 if(op == 1)
239 {
240 int u, v, add;
241 scanf("%d%d%d", &u, &v, &add);
242 update_add(u, v, add);
243 }
244 else if(op == 2)
245 {
246 int u, v;
247 scanf("%d%d", &u, &v);
248 printf("%d\n", querymax(u, v));
249 }
250 else if(op == 3)
251 {
252 int u, v;
253 scanf("%d%d", &u, &v);
254 printf("%d\n", querysum(u, v));
255 }
256 else if(op == 4)
257 {
258 int u, add;
259 scanf("%d%d", &u, &add);
260 st.update(1, 1, n, id[u], id[u]+size[u]-1, add);
261 }
262 else if(op == 5)
263 {
264 int u;
265 scanf("%d", &u);
266 printf("%d\n",st.query1(1, 1, n, 0, id[u], id[u]+size[u]-1));
267 }
268 else
269 {
270 int u;
271 scanf("%d", &u);
272 printf("%d\n",st.query2(1, 1, n, 0, id[u], id[u]+size[u]-1));
273 }
274 }
275 return 0;
276 } View Code
參考連結：
1. https://oi-wiki.org/graph/heavy-light-decomposition/
個性簽名：時間會解決一切