樹鏈剖分用一句話概括就是：把一棵樹剖分為若干條鏈，然後利用數據結構(樹狀數組，SBT，Splay，線段樹等等)去維護每一 條鏈，復雜度為O(logn) 那麼，樹鏈剖分的第一步當然是對樹進行輕重邊的劃分。 定義size(x)為以x為根的子樹節點個數，令v為u的兒子中size值最大的節點，那麼(u,v)就是重邊，其余邊為輕邊。 當然，關於這個它有兩個重要的性質： (1)輕邊(u,v)中，size(v)<=size(u/2) (2)從根到某一點的路徑上，不超過logn條輕邊和不超過logn條重路徑。 當然，剖分過程分為兩次dfs，或者bfs也可以。 如果是兩次dfs，那麼第一次dfs就是找重邊，也就是記錄下所有的重邊。 然後第二次dfs就是連接重邊形成重鏈，具體過程就是：以根節點為起點，沿著重邊向下拓展，拉成重鏈，不在當前重鏈上的節 點，都以該節點為起點向下重新拉一條重鏈。 剖分完畢後，每條重鏈相當於一段區間，然後用數據結構去維護，把所有重鏈首尾相接，放到數據結構上，然後維護整體。 在這裡，當然有很多數組，現在我來分別介紹它們的作用： siz[]數組，用來保存以x為根的子樹節點個數 top[]數組，用來保存當前節點的所在鏈的頂端節點 son[]數組，用來保存重兒子 dep[]數組，用來保存當前節點的深度 fa[]數組，用來保存當前節點的父親 tid[]數組，用來保存樹中每個節點剖分後的新編號 rank[]數組，用來保存當前節點在線段樹中的位置 那麼，我們現在可以根據描述給出剖分的代碼： 第一次dfs：記錄所有的重邊
void dfs1(int u,int father,int d)
{
dep[u]=d;
fa[u]=father;
siz[u]=1;
for(int i=head[u];~i;i=next[i])
{
int v=to[i];
if(v!=father)
{
dfs1(v,u,d+1);
siz[u]+=siz[v];
if(son[u]==-1||siz[v]>siz[son[u]])
son[u]=v;
}
}
}
第二次dfs：連重邊成重鏈
void dfs2(int u,int tp)
{
top[u]=tp;
tid[u]=++tim;
rank[tid[u]]=u;
if(son[u]==-1) return;
dfs2(son[u],tp);
for(int i=head[u];~i;i=next[i])
{
int v=to[i];
if(v!=son[u]&&v!=fa[u])
dfs2(v,v);
}
}
當然，由於題目有時候要求邊很多，所以最好不要用二維數組表示邊，應用鄰接表或者鏈式前向星。 當然，這裡面有一個重要的操作，那就是修改樹中邊權的值。 如何修改u到v的邊權的值呢？這裡有兩種情況： (1)如果u與v在同一條重鏈上，那麼就直接修改了 (2)如果u與v不在同一條重鏈上，那麼就一邊進行修改，一邊將u與v往同一條重鏈上靠，這樣就變成了第一種情況了 那麼現在的關鍵問題就是如何將u和v往同一條重鏈上靠？這個問題此處我就省略了。 至此，樹鏈剖分原理基本分析完畢！
