一、什么是樹鏈剖分

什么是樹鏈剖分？它可以把樹分成若干條鏈，從而維護(hù)樹上的路徑信息。本質(zhì)思想是把樹剖成可以用線性結(jié)構(gòu)存儲的結(jié)構(gòu)，然后可以數(shù)據(jù)結(jié)構(gòu)維護(hù)。

分為三種：重鏈剖分、長鏈剖分、實鏈剖分。以下以重鏈剖分為主。

二、樹鏈剖分的思想及能解決的問題

重鏈剖分可以將樹上的任意一條路徑劃分成不超過O(logn)條連續(xù)的鏈，每條鏈上的點深度互不相同（即是自底向上的一條鏈，鏈上所有點的LCA為鏈的一個端點）。

重鏈剖分還能保證劃分出的每條鏈上的節(jié)點DFS序連續(xù)，因此可以方便地用一些維護(hù)序列的數(shù)據(jù)結(jié)構(gòu)（如線段樹）來維護(hù)樹上路徑的信息。

相比之下，樹鏈剖分能解決的很多問題用樹上差分也能解決，兩者的關(guān)系近似于線段樹和差分的關(guān)系

如：

修改樹上兩點之間的路徑上所有點的值。

查詢樹上兩點之間的路徑上節(jié)點權(quán)值的和/極值/其它（在序列上可以用數(shù)據(jù)結(jié)構(gòu)維護(hù)，便于合并的信息）。

除了配合數(shù)據(jù)結(jié)構(gòu)來維護(hù)樹上路徑信息，樹剖還可以用來O(logn)（且常數(shù)較?。┑厍?LCA。在某些題目中，還可以利用其性質(zhì)來靈活地運用樹剖。

樹鏈剖分的核心就是把一棵樹上所有的節(jié)點轉(zhuǎn)化為一個序列，當(dāng)然樹的前序遍歷中序遍歷以及后序遍歷都可以實現(xiàn)這一目的，但是我們今天所講的是另外一種轉(zhuǎn)換方式，如果我們能把樹中任意兩個節(jié)點之間的路徑轉(zhuǎn)換為我們所求序列中幾段連續(xù)的區(qū)間我們不就可以用線段樹來實現(xiàn)區(qū)間修改以及查詢了嗎？而樹鏈剖分的實現(xiàn)方式可以保證我們把樹中任意兩點之間的路徑轉(zhuǎn)換為不超過logn段序列里面的連續(xù)區(qū)間，其中n為樹的節(jié)點個數(shù)。

（一）、重鏈剖分

1. 定義

重子節(jié)點：其子節(jié)點中子樹最大的子結(jié)點。如果有多個子樹最大的子結(jié)點，取其一。如果沒有子節(jié)點，就無重子節(jié)點。

輕子節(jié)點：除了重子節(jié)點的所有子節(jié)點。

重邊：從任意節(jié)點到重子節(jié)點的邊。

輕邊：從任意節(jié)點到輕子節(jié)點的邊。

重鏈：若干條首尾銜接的重邊，也包括了落單的節(jié)點。

如下圖 給出了具體的解釋

2. 實現(xiàn)

樹剖的實現(xiàn)分兩個DFS的過程。偽代碼如下：

第一個DFS記錄每個結(jié)點的父節(jié)點（father）、深度（deep）、子樹大?。╯ize）、重子節(jié)點（hson）。

第二個 DFS 記錄所在鏈的鏈頂（top，應(yīng)初始化為結(jié)點本身）、重邊優(yōu)先遍歷時的 DFS 序（dfn）、DFS 序?qū)?yīng)的節(jié)點編號（rank）。

以下為代碼實現(xiàn)。

為了剖出上述重鏈，我們先給出一些定義：

fa[x]：節(jié)點x在樹上的父親。

dep[x]：節(jié)點x在樹上的深度。

siz[x]：節(jié)點x的子樹節(jié)點個數(shù)。

son[x]：節(jié)點x的重兒子下標(biāo)。

top[x]：節(jié)點x所在的重鏈的頂部（深度最?。┕?jié)點。

dfn[x]：節(jié)點x的DFS序，即相當(dāng)于用數(shù)據(jù)結(jié)構(gòu)維護(hù)時的原始下標(biāo)。

rnk[x]：dfn反向映射，rnk[dfn[x]]=x。

由兩次DFS即可處理出這些信息，第一次處理前四項，后一次處理后四項。

void dfs1(int o) {
  son[o] = -1;
  siz[o] = 1;
  for (int j = h[o]; j; j = nxt[j])
    if (!dep[p[j]]) {
      dep[p[j]] = dep[o] + 1;
      fa[p[j]] = o;
      dfs1(p[j]);
      siz[o] += siz[p[j]];
      if (son[o] == -1 || siz[p[j]] > siz[son[o]]) son[o] = p[j];
    }
}

void dfs2(int o, int t) {
  top[o] = t;
  cnt++;
  dfn[o] = cnt;
  rnk[cnt] = o;
  if (son[o] == -1) return;
  dfs2(son[o], t);  // 優(yōu)先對重兒子進(jìn)行 DFS，可以保證同一條重鏈上的點 DFS 序連續(xù)
  for (int j = h[o]; j; j = nxt[j])
    if (p[j] != son[o] && p[j] != fa[o]) dfs2(p[j], p[j]);
}

（二）長鏈剖分

長鏈剖分本質(zhì)上就是另外一種鏈剖分方式。

重子節(jié)點：表示其子節(jié)點中子樹深度最大的子結(jié)點。如果有多個子樹最大的子結(jié)點，取其一。如果沒有子節(jié)點，就無重子節(jié)點。

輕子節(jié)點：表示剩余的子結(jié)點。

重邊：從這個結(jié)點到重子節(jié)點的邊。

輕邊：到其他輕子節(jié)點的邊。

重鏈：若干條首尾銜接的重邊構(gòu)成。

把落單的結(jié)點也當(dāng)作重鏈，那么整棵樹就被剖分成若干條重鏈。

如圖（這種剖分方式既可以看成重鏈剖分也可以看成長鏈剖分）：

長鏈剖分實現(xiàn)方式和重鏈剖分類似，本篇文章就不在詳細(xì)介紹了，大家可以通過練習(xí)來區(qū)分和應(yīng)用。