樹鏈剖分

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

樹鏈剖分用於將樹分割成若干條鏈的形式，以維護樹上路徑的信息。

具體來説，將整棵樹剖分為若干條鏈，使它組合成線性結構，然後用其他的數據結構維護信息。

樹鏈剖分（樹剖/鏈剖）有多種形式，如 重鏈剖分，長鏈剖分 和用於 Link/cut Tree 的剖分（有時被稱作「實鏈剖分」），大多數情況下（沒有特別説明時），「樹鏈剖分」都指「重鏈剖分」。

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

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

如：

修改 樹上兩點之間的路徑上 所有點的值。
查詢 樹上兩點之間的路徑上 節點權值的 和/極值/其它（在序列上可以用數據結構維護，便於合併的信息）。

除了配合數據結構來維護樹上路徑信息，樹剖還可以用來 \(O(\log n)\)（且常數較小）地求 LCA。在某些題目中，還可以利用其性質來靈活地運用樹剖。

重鏈剖分

我們給出一些定義：

定義 重子節點 表示其子節點中子樹最大的子結點。如果有多個子樹最大的子結點，取其一。如果沒有子節點，就無重子節點。

定義 輕子節點 表示剩餘的所有子結點。

從這個結點到重子節點的邊為重邊。

到其他輕子節點的邊為輕邊。

若干條首尾銜接的重邊構成重鏈。

把落單的結點也當作重鏈，那麼整棵樹就被剖分成若干條重鏈。

如圖：

HLD

實現

樹剖的實現分兩個 DFS 的過程。偽代碼如下：

第一個 DFS 記錄每個結點的父節點（father）、深度（deep）、子樹大小（size）、重子節點（hson）。

\[ \begin{array}{l} \text{TREE-BUILD }(u,dep) \\ \begin{array}{ll} 1 & u.hson\gets 0 \\ 2 & u.hson.size\gets 0 \\ 3 & u.deep\gets dep \\ 4 & u.size\gets 1 \\ 5 & \textbf{for }\text{each }u\text{'s son }v \\ 6 & \qquad u.size\gets u.size + \text{TREE-BUILD }(v,dep+1) \\ 7 & \qquad v.father\gets u \\ 8 & \qquad \textbf{if }v.size> u.hson.size \\ 9 & \qquad \qquad u.hson\gets v \\ 10 & \textbf{return } u.size \end{array} \end{array} \]

第二個 DFS 記錄所在鏈的鏈頂（top，應初始化為結點本身）、重邊優先遍歷時的 DFS 序（dfn）、DFS 序對應的節點編號（rank）。

\[ \begin{array}{l} \text{TREE-DECOMPOSITION }(u,top) \\ \begin{array}{ll} 1 & u.top\gets top \\ 2 & tot\gets tot+1\\ 3 & u.dfn\gets tot \\ 4 & rank(tot)\gets u \\ 5 & \textbf{if }u.hson\text{ is not }0 \\ 6 & \qquad \text{TREE-DECOMPOSITION }(u.hson,top) \\ 7 & \qquad \textbf{for }\text{each }u\text{'s son }v \\ 8 & \qquad \qquad \textbf{if }v\text{ is not }u.hson \\ 9 & \qquad \qquad \qquad \text{TREE-DECOMPOSITION }(v,v) \end{array} \end{array} \]

以下為代碼實現。

我們先給出一些定義：

\(fa(x)\) 表示節點 \(x\) 在樹上的父親。
\(dep(x)\) 表示節點 \(x\) 在樹上的深度。
\(siz(x)\) 表示節點 \(x\) 的子樹的節點個數。
\(son(x)\) 表示節點 \(x\) 的 重兒子。
\(top(x)\) 表示節點 \(x\) 所在重鏈的頂部節點（深度最小）。
\(dfn(x)\) 表示節點 \(x\) 的 DFS 序，也是其在線段樹中的編號。
\(rnk(x)\) 表示 DFS 序所對應的節點編號，有 \(rnk(dfn(x))=x\)。

我們進行兩遍 DFS 預處理出這些值，其中第一次 DFS 求出 \(fa(x)\)，\(dep(x)\)，\(siz(x)\)，\(son(x)\)，第二次 DFS 求出 \(top(x)\)，\(dfn(x)\)，\(rnk(x)\)。

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);  // 優先對重兒子進行 DFS，可以保證同一條重鏈上的點 DFS 序連續
  for (int j = h[o]; j; j = nxt[j])
    if (p[j] != son[o] && p[j] != fa[o]) dfs2(p[j], p[j]);
}

重鏈剖分的性質

樹上每個節點都屬於且僅屬於一條重鏈。

重鏈開頭的結點不一定是重子節點（因為重邊是對於每一個結點都有定義的）。

所有的重鏈將整棵樹 完全剖分。

在剖分時 重邊優先遍歷，最後樹的 DFS 序上，重鏈內的 DFS 序是連續的。按 DFN 排序後的序列即為剖分後的鏈。

一顆子樹內的 DFS 序是連續的。

可以發現，當我們向下經過一條輕邊時，所在子樹的大小至少會除以二。

因此，對於樹上的任意一條路徑，把它拆分成從 LCA 分別向兩邊往下走，分別最多走 \(O(\log n)\) 次，因此，樹上的每條路徑都可以被拆分成不超過 \(O(\log n)\) 條重鏈。

常見應用

路徑上維護

用樹鏈剖分求樹上兩點路徑權值和，偽代碼如下：

\[ \begin{array}{l} \text{TREE-PATH-SUM }(u,v) \\ \begin{array}{ll} 1 & tot\gets 0 \\ 2 & \textbf{while }u.top\text{ is not }v.top \\ 3 & \qquad \textbf{if }u.top.deep< v.top.deep \\ 4 & \qquad \qquad \text{SWAP}(u, v) \\ 5 & \qquad tot\gets tot + \text{sum of values between }u\text{ and }u.top \\ 6 & \qquad u\gets u.top.father \\ 7 & tot\gets tot + \text{sum of values between }u\text{ and }v \\ 8 & \textbf{return } tot \end{array} \end{array} \]

鏈上的 DFS 序是連續的，可以使用線段樹、樹狀數組維護。

每次選擇深度較大的鏈往上跳，直到兩點在同一條鏈上。

同樣的跳鏈結構適用於維護、統計路徑上的其他信息。

子樹維護

有時會要求，維護子樹上的信息，譬如將以 \(x\) 為根的子樹的所有結點的權值增加 \(v\)。

在 DFS 搜索的時候，子樹中的結點的 DFS 序是連續的。

每一個結點記錄 bottom 表示所在子樹連續區間末端的結點。

這樣就把子樹信息轉化為連續的一段區間信息。

求最近公共祖先

不斷向上跳重鏈，當跳到同一條重鏈上時，深度較小的結點即為 LCA。

向上跳重鏈時需要先跳所在重鏈頂端深度較大的那個。

參考代碼：

int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]])
      u = fa[top[u]];
    else
      v = fa[top[v]];
  }
  return dep[u] > dep[v] ? v : u;
}

怎麼有理有據地卡樹剖

一般情況下樹剖的 \(O(\log n)\) 常數不滿很難卡，如果要卡只能建立二叉樹深度低。

於是我們可以考慮折中方案。

我們建立一顆 \(\sqrt{n}\) 個節點的二叉樹。對於每個節點到其兒子的邊，我們將其替換成一條長度為 \(\sqrt{n}\) 的鏈。

這樣子我們可以將隨機詢問輕重鏈切換次數卡到平均 \(\frac{\log n}{2}\) 次，同時有 \(O(\sqrt{n} \log n)\) 的深度。

加上若干隨機葉子看上去可以卡樹剖。但是樹剖常數小有可能卡不掉。

例題

「ZJOI2008」樹的統計

題目大意

對一棵有 \(n\) 個節點，節點帶權值的靜態樹，進行三種操作共 \(q\) 次：

修改單個節點的權值；
查詢 \(u\) 到 \(v\) 的路徑上的最大權值；
查詢 \(u\) 到 \(v\) 的路徑上的權值之和。

保證 \(1\le n\le 30000\)，\(0\le q\le 200000\)。

解法

根據題面以及以上的性質，你的線段樹需要維護三種操作：

單點修改；
區間查詢最大值；
區間查詢和。

單點修改很容易實現。

由於子樹的 DFS 序連續（無論是否樹剖都是如此），修改一個節點的子樹只用修改這一段連續的 DFS 序區間。

問題是如何修改/查詢兩個節點之間的路徑。

考慮我們是如何用 倍增法求解 LCA 的。首先我們 將兩個節點提到同一高度，然後將兩個節點一起向上跳。對於樹鏈剖分也可以使用這樣的思想。

在向上跳的過程中，如果當前節點在重鏈上，向上跳到重鏈頂端，如果當前節點不在重鏈上，向上跳一個節點。如此直到兩節點相同。沿途更新/查詢區間信息。

對於每個詢問，最多經過 \(O(\log n)\) 條重鏈，每條重鏈上線段樹的複雜度為 \(O(\log n)\)，因此總時間複雜度為 \(O(n\log n+q\log^2 n)\)。實際上重鏈個數很難達到 \(O(\log n)\)（可以用完全二叉樹卡滿），所以樹剖在一般情況下常數較小。

給出一種代碼實現：

// st 是線段樹結構體
int querymax(int x, int y) {
  int ret = -inf, fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] >= dep[fy])
      ret = max(ret, st.query1(1, 1, n, dfn[fx], dfn[x])), x = fa[fx];
    else
      ret = max(ret, st.query1(1, 1, n, dfn[fy], dfn[y])), y = fa[fy];
    fx = top[x];
    fy = top[y];
  }
  if (dfn[x] < dfn[y])
    ret = max(ret, st.query1(1, 1, n, dfn[x], dfn[y]));
  else
    ret = max(ret, st.query1(1, 1, n, dfn[y], dfn[x]));
  return ret;
}

參考代碼

#include <algorithm>
#include <cstdio>
#include <cstring>
#define lc o << 1
#define rc o << 1 | 1
const int maxn = 60010;
const int inf = 2e9;
int n, a, b, w[maxn], q, u, v;
int cur, h[maxn], nxt[maxn], p[maxn];
int siz[maxn], top[maxn], son[maxn], dep[maxn], fa[maxn], dfn[maxn], rnk[maxn],
    cnt;
char op[10];

void add_edge(int x, int y) {  // 加边
  cur++;
  nxt[cur] = h[x];
  h[x] = cur;
  p[cur] = y;
}

struct SegTree {
  int sum[maxn * 4], maxx[maxn * 4];

  void build(int o, int l, int r) {
    if (l == r) {
      sum[o] = maxx[o] = w[rnk[l]];
      return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    sum[o] = sum[lc] + sum[rc];
    maxx[o] = std::max(maxx[lc], maxx[rc]);
  }

  int query1(int o, int l, int r, int ql, int qr) {  // 查询 max
    if (l > qr || r < ql) return -inf;
    if (ql <= l && r <= qr) return maxx[o];
    int mid = (l + r) >> 1;
    return std::max(query1(lc, l, mid, ql, qr), query1(rc, mid + 1, r, ql, qr));
  }

  int query2(int o, int l, int r, int ql, int qr) {  // 查询 sum
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[o];
    int mid = (l + r) >> 1;
    return query2(lc, l, mid, ql, qr) + query2(rc, mid + 1, r, ql, qr);
  }

  void update(int o, int l, int r, int x, int t) {  // 更新
    if (l == r) {
      maxx[o] = sum[o] = t;
      return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
      update(lc, l, mid, x, t);  // 左右分别更新
    else
      update(rc, mid + 1, r, x, t);
    sum[o] = sum[lc] + sum[rc];
    maxx[o] = std::max(maxx[lc], maxx[rc]);
  }
} st;

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);
  for (int j = h[o]; j; j = nxt[j])
    if (p[j] != son[o] && p[j] != fa[o]) dfs2(p[j], p[j]);
}

int querymax(int x, int y) {  // 查询，看main函数理解一下
  int ret = -inf, fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] >= dep[fy])
      ret = std::max(ret, st.query1(1, 1, n, dfn[fx], dfn[x])), x = fa[fx];
    else
      ret = std::max(ret, st.query1(1, 1, n, dfn[fy], dfn[y])), y = fa[fy];
    fx = top[x];
    fy = top[y];
  }
  if (dfn[x] < dfn[y])
    ret = std::max(ret, st.query1(1, 1, n, dfn[x], dfn[y]));
  else
    ret = std::max(ret, st.query1(1, 1, n, dfn[y], dfn[x]));
  return ret;
}

int querysum(int x, int y) {
  int ret = 0, fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] >= dep[fy])
      ret += st.query2(1, 1, n, dfn[fx], dfn[x]), x = fa[fx];
    else
      ret += st.query2(1, 1, n, dfn[fy], dfn[y]), y = fa[fy];
    fx = top[x];
    fy = top[y];
  }
  if (dfn[x] < dfn[y])
    ret += st.query2(1, 1, n, dfn[x], dfn[y]);
  else
    ret += st.query2(1, 1, n, dfn[y], dfn[x]);
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++)
    scanf("%d%d", &a, &b), add_edge(a, b), add_edge(b, a);
  for (int i = 1; i <= n; i++) scanf("%d", w + i);
  dep[1] = 1;
  dfs1(1);
  dfs2(1, 1);
  st.build(1, 1, n);
  scanf("%d", &q);
  while (q--) {
    scanf("%s%d%d", op, &u, &v);
    if (!strcmp(op, "CHANGE")) st.update(1, 1, n, dfn[u], v);
    if (!strcmp(op, "QMAX")) printf("%d\n", querymax(u, v));
    if (!strcmp(op, "QSUM")) printf("%d\n", querysum(u, v));
  }
  return 0;
}

Nauuo and Binary Tree

這是一道交互題，也是樹剖的非傳統應用。

題目大意

有一棵以 \(1\) 為根的二叉樹，你可以詢問任意兩點之間的距離，求出每個點的父親。

節點數不超過 \(3000\)，你最多可以進行 \(30000\) 次詢問。

解法

首先可以通過 \(n-1\) 次詢問確定每個節點的深度。

然後考慮按深度從小到大確定每個節點的父親，這樣的話確定一個節點的父親時其所有祖先一定都是已知的。

確定一個節點的父親之前，先對樹已知的部分進行重鏈剖分。

假設我們需要在子樹 \(u\) 中找節點 \(k\) 所在的位置，我們可以詢問 \(k\) 與 \(u\) 所在重鏈的尾端的距離，就可以進一步確定 \(k\) 的位置，具體見圖：

其中紅色虛線是一條重鏈，\(d\) 是詢問的結果即 \(dis(k, bot[u])\)，\(v\) 的深度為 \((dep[k]+dep[bot[u]]-d)/2\)。

這樣的話，如果 \(v\) 只有一個兒子，\(k\) 的父親就是 \(v\)，否則可以遞歸地在 \(w\) 的子樹中找 \(k\) 的父親。

時間複雜度 \(O(n^2)\)，詢問複雜度 \(O(n\log n)\)。

具體地，設 \(T(n)\) 為最壞情況下在一棵大小為 \(n\) 的樹中找到一個新節點的位置所需的詢問次數，可以得到：

\[ T(n)\le \begin{cases} 0&n=1\\ T\left(\left\lfloor\frac{n-1}2\right\rfloor\right)+1&n\ge2 \end{cases} \]

\(2999+\sum_{i=1}^{2999}T(i)\le 29940\)，事實上這個上界是可以通過構造數據達到的，然而只要進行一些隨機擾動（如對深度進行排序時使用不穩定的排序算法），詢問次數很難超過 \(21000\) 次。

參考代碼

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 3010;

int n, fa[N], ch[N][2], dep[N], siz[N], son[N], bot[N], id[N];

int query(int u, int v) {
  printf("? %d %d\n", u, v);
  fflush(stdout);
  int d;
  scanf("%d", &d);
  return d;
}

void setFather(int u, int v) {
  fa[v] = u;
  if (ch[u][0])
    ch[u][1] = v;
  else
    ch[u][0] = v;
}

void dfs(int u) {
  if (ch[u][0]) dfs(ch[u][0]);
  if (ch[u][1]) dfs(ch[u][1]);

  siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1;

  if (ch[u][1])
    son[u] = int(siz[ch[u][0]] < siz[ch[u][1]]);
  else
    son[u] = 0;

  if (ch[u][son[u]])
    bot[u] = bot[ch[u][son[u]]];
  else
    bot[u] = u;
}

void solve(int u, int k) {
  if (!ch[u][0]) {
    setFather(u, k);
    return;
  }
  int d = query(k, bot[u]);
  int v = bot[u];
  while (dep[v] > (dep[k] + dep[bot[u]] - d) / 2) v = fa[v];
  int w = ch[v][son[v] ^ 1];
  if (w)
    solve(w, k);
  else
    setFather(v, k);
}

int main() {
  int i;

  scanf("%d", &n);

  for (i = 2; i <= n; ++i) {
    id[i] = i;
    dep[i] = query(1, i);
  }

  sort(id + 2, id + n + 1, [](int x, int y) { return dep[x] < dep[y]; });

  for (i = 2; i <= n; ++i) {
    dfs(1);
    solve(1, id[i]);
  }

  printf("!");
  for (i = 2; i <= n; ++i) printf(" %d", fa[i]);
  printf("\n");
  fflush(stdout);

  return 0;
}

長鏈剖分

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

定義 重子節點 表示其子節點中子樹深度最大的子結點。如果有多個子樹最大的子結點，取其一。如果沒有子節點，就無重子節點。

定義 輕子節點 表示剩餘的子結點。

從這個結點到重子節點的邊為重邊。

到其他輕子節點的邊為輕邊。

若干條首尾銜接的重邊構成重鏈。

把落單的結點也當作重鏈，那麼整棵樹就被剖分成若干條重鏈。

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

HLD

長鏈剖分實現方式和重鏈剖分類似，這裏就不再展開。

常見應用

首先，我們發現長鏈剖分從一個節點到根的路徑的輕邊切換條數是 \(\sqrt{n}\) 級別的。

如何構造數據將輕重邊切換次數卡滿

我們可以構造這麼一顆二叉樹 T：

假設構造的二叉樹參數為 \(D\)。

若 \(D \neq 0\), 則在左兒子構造一顆參數為 \(D-1\) 的二叉樹，在右兒子構造一個長度為 \(2D-1\) 的鏈。

若 \(D = 0\), 則我們可以直接構造一個單獨葉節點，並且結束調用。

這樣子構造一定可以將單獨葉節點到根的路徑全部為輕邊且需要 \(D^2\) 級別的節點數。

取 \(D=\sqrt{n}\) 即可。

長鏈剖分優化 DP

一般情況下可以使用長鏈剖分來優化的 DP 會有一維狀態為深度維。

我們可以考慮使用長鏈剖分優化樹上 DP。

具體的，我們每個節點的狀態直接繼承其重兒子的節點狀態，同時將輕兒子的 DP 狀態暴力合併。

CF 1009F

我們設 \(f_{i,j}\) 表示在子樹 i 內，和 i 距離為 j 的點數。

直接暴力轉移時間複雜度為 \(O(n^2)\)

我們考慮每次轉移我們直接繼承重兒子的 DP 數組和答案，並且考慮在此基礎上進行更新。

首先我們需要將重兒子的 DP 數組前面插入一個元素 1, 這代表着當前節點。

然後我們將所有輕兒子的 DP 數組暴力和當前節點的 DP 數組合並。

注意到因為輕兒子的 DP 數組長度為輕兒子所在重鏈長度，而所有重鏈長度和為 \(n\)。

也就是説，我們直接暴力合併輕兒子的總時間複雜度為 \(O(n)\)。

注意，一般情況下 DP 數組的內存分配為一條重鏈整體分配內存，鏈上不同的節點有不同的首位置指針。

DP 數組的長度我們可以根據子樹最深節點算出。

例題參考代碼：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;

struct edge {
  int to, next;
} e[N * 2];

int head[N], tot, n;
int d[N], fa[N], mx[N];
int *f[N], g[N], mxp[N];
int dfn[N];

void add(int x, int y) {
  e[++tot] = (edge){y, head[x]};
  head[x] = tot;
}

void dfs1(int x) {  // 第一次插入一个1
  d[x] = 1;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa[x]) {
      fa[e[i].to] = x;
      dfs1(e[i].to);
      d[x] = max(d[x], d[e[i].to] + 1);
      if (d[e[i].to] > d[mx[x]]) mx[x] = e[i].to;
    }
}

void dfs2(int x) {  // 第二次合并
  dfn[x] = ++*dfn;
  f[x] = g + dfn[x];
  if (mx[x]) dfs2(mx[x]);
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa[x] && e[i].to != mx[x]) dfs2(e[i].to);
}

void getans(int x) {  // 暴力合并算答案
  if (mx[x]) {
    getans(mx[x]);
    mxp[x] = mxp[mx[x]] + 1;
  }
  f[x][0] = 1;
  if (f[x][mxp[x]] <= 1) mxp[x] = 0;
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != fa[x] && e[i].to != mx[x]) {
      getans(e[i].to);
      int len = d[e[i].to];
      for (int j = 0; j <= len - 1; j++) {
        f[x][j + 1] += f[e[i].to][j];
        if (f[x][j + 1] > f[x][mxp[x]]) mxp[x] = j + 1;
        if (f[x][j + 1] == f[x][mxp[x]] && j + 1 < mxp[x]) mxp[x] = j + 1;
      }
    }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    add(x, y);
    add(y, x);
  }
  dfs1(1);
  dfs2(1);
  getans(1);
  for (int i = 1; i <= n; i++) printf("%d\n", mxp[i]);
}

當然長鏈剖分優化 DP 技巧非常多，包括但是不僅限於打標記等等。這裏不再展開。

參考租酥雨的博客。

長鏈剖分求 k 級祖先

即詢問一個點向父親跳 \(k\) 次跳到的節點。

首先我們假設我們已經預處理了每一個節點的 \(2^i\) 級祖先。

現在我們假設我們找到了詢問節點的 \(2^i\) 級祖先滿足 \(2^i \le k < 2^{i+1}\)。

我們考慮求出其所在重鏈的節點並且按照深度列入表格。假設重鏈長度為 \(d\)。

同時我們在預處理的時候找到每條重鏈的根節點的 \(1\) 到 \(d\) 級祖先，同樣放入表格。

根據長鏈剖分的性質，\(k-2^i \le 2^i \leq d\), 也就是説，我們可以 \(O(1)\) 在這條重鏈的表格上求出的這個節點的 \(k\) 級祖先。

預處理需要倍增出 \(2^i\) 次級祖先，同時需要預處理每條重鏈對應的表格。

預處理複雜度 \(O(n\log n)\), 詢問複雜度 \(O(1)\)。

練習

「洛谷 P3379」【模板】最近公共祖先（LCA）（樹剖求 LCA 無需數據結構，可以用作練習）

「JLOI2014」松鼠的新家（當然也可以用樹上差分）

「HAOI2015」樹上操作

「洛谷 P3384」【模板】重鏈剖分/樹鏈剖分

「NOI2015」軟件包管理器

「SDOI2011」染色

「SDOI2014」旅行

「POI2014」Hotel 加強版（長鏈剖分優化 DP）

攻略（長鏈剖分優化貪心）

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：GoodCoder666, Ir1d, Marcythm, ouuan, hsfzLZH1, Xeonacid, greyqz, Chrogeek, ftxj, sshwy, LuoshuiTianyi, hyp1231
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用