知識準備
1.DFS；
2.線段樹。
相信DFS大家都會，估計隻有線段樹了。
如果有不會的請點這裡：線段樹系列文章（未完）
何謂樹鍊剖分？
就是将一棵樹分成許多條鍊，使得樹中所有節點都被包含在這些鍊裡。
（換句話說：就是一種使你的代碼瞬間增加1KB的算法。）
#怎麼剖分？
1.随便剖分
随便找一個節點，将它作為鍊頭向下剖分。
2.随機剖分
随便剖分+一點特判。
3.輕重鍊剖分
将重邊（後面會講）連成鍊。
哪種方法好？
顯然，對于随機資料，三種方法沒什麼差別。
但是對于第一、二種方法，若使用刻意構造的資料去測試，則會被卡掉。
綜上所述，為了保險起見，也為了算法穩定性，我們選擇輕重鍊剖分。
輕重鍊剖分
Step1：亂七糟八的定義
- 重兒子：對于每個節點的兒子，若該兒子所在的子樹的大小是所有兒子中最大的，則稱該兒子為重兒子。每個節點有且隻有一個重兒子。
- 輕兒子：除了重兒子的節點。
- 重邊：連接配接重兒子與其父親節點的邊。
- 輕邊：連接配接輕兒子與其父親節點的邊。
- 重鍊：由重邊連接配接而成的鍊。注意鍊内有且隻有重邊。
相信你也看不懂（hhh），舉個例子吧：
如圖，在這棵樹中：紅框框着的點就是重兒子，紫色邊表示重邊，黑色邊表示輕邊。可以看出兩條重鍊：{1,2,5,6}和{3,8,9}。而且，我們發現，重鍊的起點都是輕兒子。
Step2：重标号？
然後，我們可以對所有節點進行重編号（優先重兒子），就會得到如下的結果：（藍色點即為新标号）
我們發現：重鍊中，标号都是連續的。于是，我們可以想象一下：将所有重鍊按鍊首标号進行排序，并拉直平放起來；我們就得到了一個線性的序列。
并且：我們可以發現一些性質：
性質一：對于兩個節點u，v，若v是u的輕兒子，則有：siz[v]<=siz[u]/2，若v是u的重兒子，則：siz[v]>siz[u]/2；
性質二：對于一個任意節點u，它到根節點的路徑最多有 log 2 N \log_2 N log2N條輕邊， log 2 N \log_2N log2N條重路徑。
Step3：資料結構：線段樹
接下來就很玄學了
由上一步可知，我們得到了一個序列，于是，我們就可以把這一堆東西扔給線段樹了。
我們可以進行權值修改、路徑查詢等操作，而做到這一切，都隻需要 O ( N log 2 N ) O(N\log_2N) O(Nlog2N)的時間複雜度。
實作
Step1：混亂的數組
先扔來一堆數組名字：
-
val[1...N]
-
siz[1...N]
-
top[1...N]
-
son[1...N]
-
dep[1...N]
-
tid[1...N]
-
rnk[1...N]
tid
-
fa[1...N]
暈了對吧？别慌，其實都非常有用的，了解了就非常容易。
Step2：第一次DFS
這次DFS我們主要處理一些基礎資訊，即：
siz
、
son
、
dep
和
fa
四個數組。
這種事情應該不會很困難吧？直接粘代碼了。
void DFS1(int u,int f,int d) {
dep[u]=d,fa[u]=f,siz[u]=1;
for(Tnode *p=G[u];p!=NULL;p=p->nxt) {
int v=p->v;
if(v==f)continue;
val[v]=p->w;
DFS1(v,u,d+1);
siz[u]+=siz[v];
if(son[u]==-1||siz[v]>siz[son[u]])
son[u]=v;
}
}
順便粘上一份我使用的鄰接表：
struct Tnode {
int v,w;
Tnode *nxt;
}e[2*Maxn+5];
Tnode *G[Maxn+5],*ecnt=&e[0];
void AddEdge(int u,int v,int w) {
Tnode *p=++ecnt;
p->v=v,p->w=w;
p->nxt=G[u],G[u]=p;
p=++ecnt;
p->v=u,p->w=w;
p->nxt=G[v],G[v]=p;
}
Step3：第二次DFS
這次DFS主要處理剩下的資訊：
top
、
tid
和
rnk
三個數組。
我們在DFS傳入一個參數
tp
，表示目前所在重鍊的鍊首，若遇到輕兒子則将
tp
設為該節點并繼續往下傳。
在處理
tid
，
rnk
時，我們開一個全局變量
dcnt
，每次進DFS時加一，就可以處理出這些資訊了。代碼如下：
void DFS2(int u,int tp) {
top[u]=tp,tid[u]=++dcnt,rnk[dcnt]=u;
if(son[u]==-1)
return;
DFS2(son[u],tp);
for(Tnode *p=G[u];p!=NULL;p=p->nxt) {
int v=p->v;
if(v==son[u]||v==fa[u])
continue;
DFS2(v,v);
}
}
做完這些後，我們就完成了整個樹鍊剖分的實作。
剩下的就是各種資料結構的事情了。
例題選講
例題1：SPOJ QTREE Query on a Tree