前言
- 樹鍊剖分是什麼？
樹鍊剖分，說白了就是一種讓你代碼不得不強行增加1k的資料結構-dms
個人了解：+1:joy:
- 有什麼用？
證明出題人非常毒瘤
可以非常友(bao)好(li)的解決一些樹上問題:grimacing:
（友情提示：學樹鍊剖分之前請先掌握線段樹）
核心思想
樹鍊剖分的思想比較神奇
它的思想是：把一棵樹拆成若幹個不相交的鍊，然後用一些資料結構去維護這些鍊
那麼問題來了
- 如何把樹拆成鍊？
首先明确一些定義
重兒子：該節點的子樹中,節點個數最多的子樹的根節點(也就是和該節點相連的點)，即為該節點的重兒子
重邊：連接配接該節點與它的重兒子的邊
重鍊：由一系列重邊相連得到的鍊
輕鍊：由一系列非重邊相連得到的鍊
這樣就不難得到拆樹的方法
對于每一個節點，找出它的重兒子，那麼這棵樹就自然而然的被拆成了許多重鍊與許多輕鍊
- 如何對這些鍊進行維護？
首先，要對這些鍊進行維護，就要確定每個鍊上的節點都是連續的，
是以我們需要對整棵樹進行重新編号，然後利用dfs序的思想，用線段樹或樹狀數組等進行維護（具體用什麼需要看題目要求，因為線段樹的功能比樹狀數組強大，是以在這裡我就不提供樹狀數組的寫法了）
注意在進行重新編号的時候先通路重鍊
這樣可以保證重鍊内的節點編号連續
上面說的太抽象了，結合一張圖來了解一下
對于一棵最基本的樹
給他标記重兒子，
藍色為重兒子，紅色為重邊
然後對樹進行重新編号
橙色表示的是該節點重新編号後的序号
不難看出重鍊内的節點編号是連續的
然後就可以線上段樹上搞事情啦
像什麼區間加區間求和什麼的
另外有一個性質：以$i$為根的子樹的樹線上段樹上的編号為$[i,i+子樹節點數-1]$
接下來結合一道例題，加深一下對于代碼的了解
代碼
題目連結
樹鍊剖分的裸題
首先來一坨定義
int deep[MAXN];//節點的深度
int fa[MAXN];//節點的父親
int son[MAXN];//節點的重兒子
int tot[MAXN];//節點子樹的大小 第一步
按照我們上面說的，我們首先要對整棵樹dfs一遍，找出每個節點的重兒子
順便處理出每個節點的深度，以及他們的父親節點
int dfs1(int now, int f, int dep) {
deep[now] = dep;
fa[now] = f;
tot[now] = 1;
int maxson = -1;
for (int i = head[now]; i != -1; i = edge[i].nxt) {
if (edge[i].v == f) continue;
tot[now] += dfs1(edge[i].v, now, dep + 1);
if (tot[edge[i].v] > maxson) maxson = tot[edge[i].v], son[now] = edge[i].v;
}
return tot[now];
} 第二步
然後我們需要對整棵樹進行重新編号
我把一開始的每個節點的權值存在了$b$數組内
void dfs2(int now, int topf) {
idx[now] = ++cnt;
a[cnt] = b[now];
top[now] = topf;
if (!son[now]) return ;
dfs2(son[now], topf);
for (int i = head[now]; i != -1; i = edge[i].nxt)
if (!idx[edge[i].v])
dfs2(edge[i].v, edge[i].v);
} $idx$表示重新編号後該節點的編号是多少
另外，這裡引入了一個$top$數組，
$top[i]$表示$i$号節點所在重鍊的頭節點(最頂上的節點)
至于這個數組有啥用，後面再說
第三步
我們需要根據重新編完号的樹，把這棵樹的上每個點映射到線段樹上，
struct Tree {
int l, r, w, siz, f;
} T[MAXN]; void Build(int k, int ll, int rr) {
T[k].l = ll; T[k].r = rr; T[k].siz = rr - ll + 1;
if (ll == rr) {
T[k].w = a[ll];
return ;
}
int mid = (ll + rr) >> 1;
Build(ls, ll, mid);
Build(rs, mid + 1, rr);
update(k);
} 另外線段樹的基本操作，
這裡就不詳細解釋了
直接放代碼
void update(int k) { //更新
T[k].w = (T[ls].w + T[rs].w + MOD) % MOD;
}
void IntervalAdd(int k, int ll, int rr, int val) { //區間加
if (ll <= T[k].l && T[k].r <= rr) {
T[k].w += T[k].siz * val;
T[k].f += val;
return ;
}
pushdown(k);
int mid = (T[k].l + T[k].r) >> 1;
if (ll <= mid) IntervalAdd(ls, ll, rr, val);
if (rr > mid) IntervalAdd(rs, ll, rr, val);
update(k);
}
int IntervalSum(int k, int ll, int rr) { //區間求和
int ans = 0;
if (ll <= T[k].l && T[k].r <= rr)
return T[k].w;
pushdown(k);
int mid = (T[k].l + T[k].r) >> 1;
if (ll <= mid) ans = (ans + IntervalSum(ls, ll, rr)) % MOD;
if (rr > mid) ans = (ans + IntervalSum(rs, ll, rr)) % MOD;
return ans;
}
void pushdown(int k) { //下傳标記
if (!T[k].f) return ;
T[ls].w = (T[ls].w + T[ls].siz * T[k].f) % MOD;
T[rs].w = (T[rs].w + T[rs].siz * T[k].f) % MOD;
T[ls].f = (T[ls].f + T[k].f) % MOD;
T[rs].f = (T[rs].f + T[k].f) % MOD;
T[k].f = 0;
} 第四步
我們考慮如何實作對于樹上的操作
樹鍊剖分的思想是:對于兩個不在同一重鍊内的節點,讓他們不斷地跳,使得他們處于同一重鍊上
那麼如何"跳”呢？
還記得我們在第二次$dfs$中記錄的$top$數組麼？
有一個顯然的結論：$x$到$top[x]$中的節點線上段樹上是連續的，
結合$deep$數組
假設兩個節點為$x$,$y$
我們每次讓$deep[top[x]]$與$deep[top[y]]$中大的(在下面的)往上跳(有點類似于樹上倍增)
讓x節點直接跳到$top[x]$,然後線上段樹上更新
最後兩個節點一定是處于同一條重鍊的，前面我們提到過重鍊上的節點都是連續的，直接線上段樹上進行一次查詢就好
void TreeSum(int x, int y) { //x與y路徑上的和
int ans = 0;
while (top[x] != top[y]) {
if (deep[top[x]] < deep[top[y]]) swap(x, y);
ans = (ans + IntervalSum(1, idx[ top[x] ], idx[x])) % MOD;
x = fa[ top[x] ];
}
if (deep[x] > deep[y]) swap(x, y);
ans = (ans + IntervalSum(1, idx[x], idx[y])) % MOD;
printf("%d\n", ans);
}
void TreeAdd(int x, int y, int val) { //對于x,y路徑上的點加val的權值
while (top[x] != top[y]) {
if (deep[top[x]] < deep[top[y]]) swap(x, y);
IntervalAdd(1, idx[ top[x] ], idx[x], val);
x = fa[ top[x] ];
}
if (deep[x] > deep[y]) swap(x, y);
IntervalAdd(1, idx[x], idx[y], val);
} 在樹上查詢的這一步可能有些抽象，我們結合一個例子來了解一下
還是上面那張圖，假設我們要查詢$3.6$這兩個節點的之間的點權合，為了友善了解我們假設每個點的點權都是$1$
剛開始時
$top[3]=2,top[6]=1$
$deep[top[3]]=2,deep[top[6]]=1$
我們會讓$3$向上跳,跳到$top[3]$的爸爸,也就是$1$号節點
這是$1$号節點和$6$号節點已經在同一條重鍊内,是以直接對線段樹進行一次查詢即可
對于子樹的操作
這個就更簡單了
因為一棵樹的子樹線上段樹上是連續的
是以修改的時候直接這樣
IntervalAdd(1,idx[x],idx[x]+tot[x]-1,z%MOD); 時間複雜度
(剛開始忘記寫了,這一塊是後來補上的)
性質1
如果邊$\left( u,v\right)$,為輕邊,那麼$Size\left( v\right) \leq Size\left( u\right) /2$。
證明：顯然:joy:，否則該邊會成為重邊
性質2
樹中任意兩個節點之間的路徑中輕邊的條數不會超過$\log _{2}n$,重路徑的數目不會超過$\log _{2}n$
證明：不會:stuck_out_tongue_winking_eye:
有了上面兩條性質，我們就可以來分析時間複雜度了
由于重路徑的數量的上界為$\log _{2}n$，
線段樹中查詢/修改的複雜度為$\log _{2}n$
那麼總的複雜度就是$\left( \log _{2}n\right) ^{2}$
例題
洛谷P3379 【模闆】最近公共祖先（LCA）
樹剖可以求LCA，沒想到吧
http://www.cnblogs.com/zwfymqz/p/8097366.html
洛谷P2590 [ZJOI2008]樹的統計
http://www.cnblogs.com/zwfymqz/p/7157156.html
這份代碼是以前寫的，可能比較醜，下面兩份是剛剛寫的
洛谷P3178 [HAOI2015]樹上操作
http://www.cnblogs.com/zwfymqz/p/8094286.html
洛谷P3038 [USACO11DEC]牧草種植Grass Planting
有點意思
http://www.cnblogs.com/zwfymqz/p/8094429.html
作者：自為風月馬前卒
個人部落格http://attack204.com//
出處：http://zwfymqz.cnblogs.com/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。