"什麼是 LCA（最近公共祖先）？"

"LCA 是兩個節點在樹中共同的最深祖先。例如在家族樹中，你和你表兄弟的 LCA 就是你們共同的祖父母。LCA 用倍增法預處理 O(n log n)，查詢 O(log n)；用 Euler Tour + Sparse Table 可以做到 O(1) 查詢。"

"樹 DP 和普通 DP 有什麼不同？"

"樹 DP 的狀態定義在樹的節點上，轉移方向沿著父子關係（通常是後序遍歷，從葉子往根匯總）。常見問題：樹的直徑、樹的最大路徑和、打家劫舍 III。轉移方程通常是 dp[node] = f(dp[child1], dp[child2], ...)。"

"重鏈剖分有什麼用？"

"重鏈剖分將樹分解為若干重鏈，每條鏈上的節點在 DFS 序中連續。搭配線段樹，可以在 O(log²n) 時間內完成樹上路徑查詢和修改。常用於競程中的樹上區間問題。"

樹演算法 — LCA、樹 DP 與重鏈剖分進階技巧 | 資料結構與演算法

樹演算法（Tree Algorithms） 是競技程式設計中最精深的技術之一。從 LCA 最近公共祖先 的倍增法，到 樹上動態規劃 的後序匯總，再到 重鏈剖分 的路徑區間查詢，這些技巧在版本控制系統、DOM 樹查詢、網路拓撲分析中都有實際應用。本文帶你從原理到 TypeScript 與 C++ 完整實作，一次掌握進階樹演算法。

前言

當你呼叫 git merge-base A B 找出兩個分支的共同祖先 Commit 時，背後就是一個 LCA（Lowest Common Ancestor，最近公共祖先） 的查詢。當瀏覽器引擎處理 CSS 選擇器中的祖先關係判斷時，用的是 Euler Tour + 區間包含 的技巧。

樹演算法的應用場景遠比你想像的廣泛。學習本文後，你將能夠：

理解並實作 LCA 倍增法（Binary Lifting）——預處理 O(N log N)，查詢 O(log N)
掌握 樹 DP 的後序遍歷框架，解決樹的直徑、獨立集等問題
了解 Euler Tour 如何將樹問題轉化為陣列區間問題
認識 重鏈剖分（HLD） 與 重心分治 的核心思路
能在面試中流利解決 LeetCode 236、543、337、124、1483

核心概念

LCA：最近公共祖先

LCA(u, v) 定義為節點 u 與 v 在樹中共同祖先裡，深度最大（即最接近葉子方向）的那個節點。用家族樹比喻：你和表兄弟的 LCA 就是你們共同的祖父母。

三種主要解法的對比：

方法	預處理時間	查詢時間	空間	適用場景
暴力法	O(N)	O(N)	O(N)	樹高度小、查詢次數少
倍增法（Binary Lifting）	O(N log N)	O(log N)	O(N log N)	通用首選
Euler Tour + RMQ	O(N log N)	O(1)	O(N log N)	查詢極多、對常數敏感

倍增法的核心思想：預處理每個節點向上跳 2⁰、2¹、2²、…、2^k 步的祖先，存放在 anc[node][k] 中。查詢時利用二進位分解（Binary Decomposition），先同步兩節點深度，再同時向上跳直到找到 LCA。

            1  (depth=0)
           / \
          2   3  (depth=1)
         / \   \
        4   5   6  (depth=2)
       / \
      7   8  (depth=3)

查詢 LCA(7, 6)：
  depth[7]=3, depth[6]=2 → 7先跳1步到4
  depth[4]=2, depth[6]=2 → 深度相同
  嘗試跳2步：anc[4][1]=1, anc[6][1]=1 → 相同，不跳
  嘗試跳1步：anc[4][0]=2, anc[6][0]=3 → 不同，跳！
  4→2, 6→3（仍不同），再跳一步
  2→1, 3→1 → 相同，LCA = 1 ✓

樹 DP：後序遍歷框架

樹 DP（Tree DP） 的狀態定義在節點上，轉移沿著父子關係進行。核心框架是 後序遍歷（Post-order）：先遞迴計算所有子節點的 dp 值，再由子節點匯總到父節點。

以最大獨立集為例：

dp[u][1] = 選取節點 u 時，u 的子樹中最大獨立集大小
dp[u][0] = 不選節點 u 時，u 的子樹中最大獨立集大小
轉移：dp[u][1] += dp[v][0]，dp[u][0] += max(dp[v][0], dp[v][1])（v 為 u 的子節點）

Euler Tour 與 DFS 序

Euler Tour 對樹進行 DFS，每次「進入」和「離開」節點時都記錄，得到長度 2N-1 的序列。利用此序列：

LCA(u, v) = Euler Tour 中 first[u] 到 first[v] 區間內深度最小的節點
搭配 Sparse Table 可做到 O(N log N) 預處理、O(1) 查詢

DFS 序（Euler Order） 則只在進入節點時記錄，產生長度 N 的陣列，常用於判斷「u 是否為 v 的祖先」（區間包含關係），也是重鏈剖分的基礎。

JavaScript / TypeScript 實作

LCA 倍增法（Binary Lifting）

class LCABinaryLifting {
  private LOG: number;
  private depth: number[];
  private anc: number[][]; // anc[node][k] = node向上跳2^k步的祖先
  private adj: number[][];

  constructor(n: number, edges: [number, number][], root: number = 0) {
    this.LOG = Math.ceil(Math.log2(n + 1)) + 1;
    this.depth = new Array(n).fill(0);
    this.adj = Array.from({ length: n }, () => []);
    // anc[node][k] = -1 表示不存在（超出根節點）
    this.anc = Array.from({ length: n }, () => new Array(this.LOG).fill(-1));

    for (const [u, v] of edges) {
      this.adj[u].push(v);
      this.adj[v].push(u);
    }

    this.dfsPreprocess(root, -1, 0);
  }

  private dfsPreprocess(u: number, parent: number, d: number): void {
    this.depth[u] = d;
    this.anc[u][0] = parent; // 向上跳1步（2^0）的祖先

    // 遞推：向上跳2^k步 = 先跳2^(k-1)步，再跳2^(k-1)步
    for (let k = 1; k < this.LOG; k++) {
      const mid = this.anc[u][k - 1];
      this.anc[u][k] = mid === -1 ? -1 : this.anc[mid][k - 1];
    }

    for (const v of this.adj[u]) {
      if (v !== parent) {
        this.dfsPreprocess(v, u, d + 1);
      }
    }
  }

  // 讓節點u向上跳k步，返回目標祖先
  private kthAncestor(u: number, k: number): number {
    for (let bit = 0; bit < this.LOG; bit++) {
      if ((k >> bit) & 1) {
        u = this.anc[u][bit];
        if (u === -1) return -1;
      }
    }
    return u;
  }

  // 查詢LCA(u, v)
  query(u: number, v: number): number {
    // 確保u比v深（或相同）
    if (this.depth[u] < this.depth[v]) [u, v] = [v, u];

    // 同步深度：讓u跳到與v相同的深度
    u = this.kthAncestor(u, this.depth[u] - this.depth[v]);

    if (u === v) return u; // v是u的祖先，LCA就是v

    // 二進位分解：找到LCA的子節點
    for (let k = this.LOG - 1; k >= 0; k--) {
      if (this.anc[u][k] !== this.anc[v][k]) {
        u = this.anc[u][k];
        v = this.anc[v][k];
      }
    }

    return this.anc[u][0]; // LCA = u（或v）的父節點
  }

  // 查詢u到v的路徑長度（邊數）
  distance(u: number, v: number): number {
    const lca = this.query(u, v);
    return this.depth[u] + this.depth[v] - 2 * this.depth[lca];
  }
}

// 使用範例
const n = 8;
const edges: [number, number][] = [
  [0,1],[0,2],[1,3],[1,4],[2,5],[3,6],[3,7]
];
const lca = new LCABinaryLifting(n, edges, 0);
console.log(lca.query(6, 5));    // 0（LCA of 6 and 5 is root 0）
console.log(lca.query(6, 7));    // 3（LCA of 6 and 7 is 3）
console.log(lca.distance(6, 5)); // 4

樹直徑（兩次 BFS）

樹直徑是樹中任意兩節點間最長路徑的邊數。演算法：從任意節點出發 BFS 找最遠節點 u，再從 u 出發 BFS 找最遠距離。

// 兩次BFS求樹直徑：O(N)
function treeDiameter(n: number, edges: [number, number][]): number {
  if (n === 1) return 0;

  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);
  }

  function bfsFarthest(start: number): [number, number] {
    // 返回 [最遠節點, 最遠距離]
    const dist = new Array(n).fill(-1);
    dist[start] = 0;
    const queue: number[] = [start];
    let head = 0, farthestNode = start, maxDist = 0;

    while (head < queue.length) {
      const u = queue[head++];
      for (const v of adj[u]) {
        if (dist[v] === -1) {
          dist[v] = dist[u] + 1;
          queue.push(v);
          if (dist[v] > maxDist) {
            maxDist = dist[v];
            farthestNode = v;
          }
        }
      }
    }
    return [farthestNode, maxDist];
  }

  // 第一次BFS：找直徑端點u
  const [u] = bfsFarthest(0);
  // 第二次BFS：從u出發找直徑長度
  const [, diameter] = bfsFarthest(u);

  return diameter;
  // 時間複雜度：O(N)；空間複雜度：O(N)
}

console.log(treeDiameter(5, [[0,1],[1,2],[2,3],[1,4]])); // 3

樹 DP：打家劫舍 III（LeetCode 337）

這是樹 DP 的經典題：不能同時選擇相鄰（父子）節點，求最大選取值。

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

// dp(node) = [不搶node的最大值, 搶node的最大值]
function rob(root: TreeNode | null): number {
  function dfs(node: TreeNode | null): [number, number] {
    if (!node) return [0, 0];

    const [leftNo, leftYes] = dfs(node.left);
    const [rightNo, rightYes] = dfs(node.right);

    // 搶node：左右子節點都不能搶
    const robThis = node.val + leftNo + rightNo;

    // 不搶node：左右子節點可搶可不搶，取最大
    const skipThis = Math.max(leftNo, leftYes) + Math.max(rightNo, rightYes);

    return [skipThis, robThis];
  }

  const [no, yes] = dfs(root);
  return Math.max(no, yes);
  // 時間複雜度：O(N)；空間複雜度：O(H)（H為樹高）
}

樹 DP：最大路徑和（LeetCode 124）

樹上最大路徑可以「不必經過根節點」，需要在每個節點計算「以此節點為轉折點的最大路徑」。

function maxPathSum(root: TreeNode | null): number {
  let globalMax = -Infinity;

  // 返回：以node為起點（向下延伸）的最大路徑和
  function dfs(node: TreeNode | null): number {
    if (!node) return 0;

    // 負值子樹不取（取0表示不走那條邊）
    const leftGain = Math.max(dfs(node.left), 0);
    const rightGain = Math.max(dfs(node.right), 0);

    // 以node為轉折點的路徑：左延伸 + node + 右延伸
    const pathThroughNode = node.val + leftGain + rightGain;
    globalMax = Math.max(globalMax, pathThroughNode);

    // 返回：只能選一側（路徑必須連續，不能分叉）
    return node.val + Math.max(leftGain, rightGain);
  }

  dfs(root);
  return globalMax;
  // 時間複雜度：O(N)；空間複雜度：O(H)
}

Euler Tour（歐拉遊覽）

// Euler Tour：進入和離開節點各記錄一次，得到長度2N-1的序列
// 用途：LCA(u,v) = 序列中first[u]到first[v]之間深度最小的節點
function buildEulerTour(
  n: number,
  edges: [number, number][],
  root: number = 0
): { tour: number[]; depth: number[]; firstOccurrence: number[] } {
  const adj: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);
  }

  const tour: number[] = [];       // Euler Tour 序列（節點索引）
  const depth: number[] = new Array(n).fill(0);
  const firstOccurrence: number[] = new Array(n).fill(-1); // first[u]

  function dfs(u: number, parent: number, d: number): void {
    depth[u] = d;
    firstOccurrence[u] = tour.length;
    tour.push(u); // 進入u

    for (const v of adj[u]) {
      if (v !== parent) {
        dfs(v, u, d + 1);
        tour.push(u); // 從v返回後再記錄u
      }
    }
  }

  dfs(root, -1, 0);
  return { tour, depth, firstOccurrence };
  // tour.length = 2N - 1
  // LCA(u, v)：在 tour[first[u]...first[v]] 中找depth最小的元素
}

C++ 對照實作

#include <bits/stdc++.h>
using namespace std;

// ===== LCA — 倍增法（Binary Lifting）=====
struct LCA {
    int n, LOG;
    vector<int> depth;
    vector<vector<int>> anc; // anc[node][k] = 向上跳2^k步的祖先
    vector<vector<int>> adj;

    LCA(int n, vector<pair<int,int>>& edges, int root = 0)
        : n(n), LOG(20), depth(n), anc(n, vector<int>(20, -1)), adj(n) {
        for (auto& [u, v] : edges) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        dfs(root, -1, 0);
    }

    void dfs(int u, int par, int d) {
        depth[u] = d;
        anc[u][0] = par;
        for (int k = 1; k < LOG; k++) {
            int mid = anc[u][k-1];
            anc[u][k] = (mid == -1) ? -1 : anc[mid][k-1];
        }
        for (int v : adj[u]) {
            if (v != par) dfs(v, u, d + 1);
        }
    }

    int kthAnc(int u, int k) {
        for (int b = 0; b < LOG; b++) {
            if ((k >> b) & 1) {
                u = anc[u][b];
                if (u == -1) return -1;
            }
        }
        return u;
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        u = kthAnc(u, depth[u] - depth[v]);
        if (u == v) return u;
        for (int k = LOG - 1; k >= 0; k--) {
            if (anc[u][k] != anc[v][k]) {
                u = anc[u][k];
                v = anc[v][k];
            }
        }
        return anc[u][0];
    }

    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
    }
};

// ===== 樹DP — 最大獨立集 =====
int maxIndependentSet(int n, vector<pair<int,int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // dp[u][0/1] = 不選/選節點u時的最大獨立集
    vector<array<int,2>> dp(n, {0, 1});
    vector<int> parent(n, -1);
    vector<int> order; // 後序順序

    // 迭代DFS（避免遞迴棧溢出）
    vector<bool> visited(n, false);
    stack<int> stk;
    stk.push(0);
    while (!stk.empty()) {
        int u = stk.top();
        if (!visited[u]) {
            visited[u] = true;
            for (int v : adj[u]) {
                if (v != parent[u]) {
                    parent[v] = u;
                    stk.push(v);
                }
            }
        } else {
            stk.pop();
            order.push_back(u);
        }
    }

    for (int u : order) {
        for (int v : adj[u]) {
            if (v == parent[u]) continue;
            dp[u][1] += dp[v][0];
            dp[u][0] += max(dp[v][0], dp[v][1]);
        }
    }

    return max(dp[0][0], dp[0][1]);
}

// ===== 重心分解（Centroid Decomposition）=====
struct CentroidDecomp {
    int n;
    vector<vector<int>> adj;
    vector<int> sz, centParent;
    vector<bool> removed;

    CentroidDecomp(int n, vector<pair<int,int>>& edges)
        : n(n), adj(n), sz(n), centParent(n, -1), removed(n, false) {
        for (auto& [u, v] : edges) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        build(0, -1);
    }

    int calcSize(int u, int par) {
        sz[u] = 1;
        for (int v : adj[u])
            if (v != par && !removed[v])
                sz[u] += calcSize(v, u);
        return sz[u];
    }

    int findCentroid(int u, int par, int treeSize) {
        for (int v : adj[u])
            if (v != par && !removed[v] && sz[v] > treeSize / 2)
                return findCentroid(v, u, treeSize);
        return u;
    }

    void build(int u, int cp) {
        int ts = calcSize(u, -1);
        int c = findCentroid(u, -1, ts);
        centParent[c] = cp;
        removed[c] = true;
        for (int v : adj[c])
            if (!removed[v])
                build(v, c);
    }
};

複雜度分析

演算法	預處理時間	查詢/操作時間	空間	備注
LCA 暴力法	O(N)	O(N)	O(N)	最壞情況為鏈狀樹
LCA 倍增法	O(N log N)	O(log N)	O(N log N)	競程首選
LCA Euler Tour + RMQ	O(N log N)	O(1)	O(N log N)	常數最優
樹 DP（後序）	O(N)	—	O(N)	大多數樹 DP 問題
樹直徑（兩次 BFS）	—	O(N)	O(N)	常數極小
重心分治	O(N log N)	O(N log N)	O(N log N)	路徑統計問題
重鏈剖分 + 線段樹	O(N log N)	O(log² N)	O(N log N)	路徑區間修改查詢

變體與延伸

重鏈剖分（Heavy-Light Decomposition，HLD）

核心思想：將樹中的邊分為兩類：

重邊（Heavy Edge）：指向子樹最大的子節點的邊
輕邊（Light Edge）：其餘邊

連續的重邊構成 重鏈（Heavy Chain）。由於每次走輕邊，子樹大小至少減半，從根到任意葉的路徑上最多有 O(log N) 條輕邊，因此重鏈數量也是 O(log N)。

關鍵應用：將每條重鏈的節點映射到線段樹（Segment Tree）的連續區間，可以在 O(log² N) 時間內回答樹上路徑查詢（路徑最大值、路徑和、路徑修改）。這是競程中解決「樹上路徑區間問題」的標準技術。

示意：一棵樹的重鏈分解
        1
       / \
      2   3    ← 重邊：1-2（子樹大小5 > 1）
     / \   \
    4   5   6  ← 重邊：2-4（子樹大小2 > 1）
   / \
  7   8

重鏈：[1-2-4-7]、[8]、[3-6]、[5]
DFS序中每條重鏈的節點連續排列 → 搭配線段樹做路徑查詢

重心分治（Centroid Decomposition）

重心：移除後，各連通塊大小均不超過原子樹大小一半的節點。每棵樹都有重心（最多兩個相鄰節點）。

重心分治的思路：

找整棵樹的重心 c，以 c 為根處理所有「經過 c 的路徑」
標記 c 已處理，遞迴對每個子樹做同樣的事
由於每次子樹大小至少減半，重心樹的高度 ≤ log₂N

用途：統計樹上所有路徑中滿足某條件（如距離恰好為 k）的路徑數。時間複雜度 O(N log N)。

原始樹（8個節點）重心分解過程：
        1
       / \
      2   3
     / \   \
    4   5   6
   /
  7
   \
    8

Step 1: 整棵樹重心 = 節點2
Step 2: 以2為根建立重心樹節點，標記2已處理
Step 3: 對子樹[1,3,6]和[4,7,8]和[5]遞迴

重心樹（高度 ≤ log₂N）：
      2
    / | \
   1  4   5
  / \ |
 3  6  7
         \
          8

面試考點

面試中樹演算法的常見問法：

LCA 的三種解法 — 能說清楚暴力法、倍增法、Euler Tour 的時間複雜度差異，以及各自適用場景
樹 DP 的狀態設計 — 如何定義 dp[node]，轉移方向是從葉到根（後序）
換根 DP（Rerooting） — 先以節點 0 為根做一次後序 DP，再用前序遍歷做換根轉移（LeetCode 834）
樹的直徑不能用 DFS 求 — 遞迴 DFS 在鏈狀樹（N=10⁵）可能棧溢出，面試時應使用迭代 BFS
Binary Lifting 的 LOG 設定 — LOG 應至少為 ceil(log₂(N)) + 1，設定過小會導致大 k 查詢錯誤

常見陷阱：

anc[root][0] 必須初始化為 -1（根節點無父節點），否則 LCA 查詢可能進入無限迴圈
Rerooting 時 subtreeSize[child] 是「以 0 為根時」的子樹大小，換根過程中不能更新它
重心分解每次遞迴前必須重新呼叫 calcSize，才能得到當前子樹（非整棵樹）的準確大小

LeetCode 練習題

題號	題目	難度	核心技巧
236	Lowest Common Ancestor of a Binary Tree	Medium	遞迴：找到兩節點分岔點
543	Diameter of Binary Tree	Easy	樹 DP：後序遍歷記錄最長路徑
337	House Robber III	Medium	樹 DP：dp[node][0/1]
124	Binary Tree Maximum Path Sum	Hard	樹 DP：轉折點技巧
1483	Kth Ancestor of a Tree Node	Hard	Binary Lifting 倍增法

LeetCode 236 — LCA of Binary Tree

// 遞迴DFS：
// 1. 若root為null或root等於p/q，直接返回root
// 2. 遞迴查詢左右子樹
// 3. 若左右都找到（非null），root就是LCA
// 4. 只有一側找到，返回那側的結果
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  if (!root || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // 左右都非null：p在左子樹，q在右子樹，root是LCA
  if (left && right) return root;

  // 只有一側找到：LCA在那側子樹中
  return left ?? right;
  // 時間複雜度：O(N)；空間複雜度：O(H)
}

LeetCode 543 — Diameter of Binary Tree

// 每個節點計算「以此節點為轉折點的最長路徑」，更新全域最大值
function diameterOfBinaryTree(root: TreeNode | null): number {
  let maxDiameter = 0;

  function dfs(node: TreeNode | null): number {
    // 返回：以node為起點往下延伸的最長路徑（邊數）
    if (!node) return 0;

    const leftDepth = dfs(node.left);
    const rightDepth = dfs(node.right);

    // 以node為轉折點的直徑 = 左最深 + 右最深
    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);

    return 1 + Math.max(leftDepth, rightDepth);
  }

  dfs(root);
  return maxDiameter;
  // 時間複雜度：O(N)；空間複雜度：O(H)
}

LeetCode 1483 — Kth Ancestor of a Tree Node

// Binary Lifting 倍增法：預處理O(N log N)，查詢O(log k)
class TreeAncestor {
  private LOG: number = 16; // 2^16 = 65536 > 5×10^4
  private anc: number[][];

  constructor(n: number, parent: number[]) {
    this.anc = Array.from({ length: n }, () => new Array(this.LOG).fill(-1));

    // 初始化：anc[node][0] = parent[node]
    for (let i = 0; i < n; i++) {
      this.anc[i][0] = parent[i]; // parent[root] = -1
    }

    // 遞推：向上跳2^k = 先跳2^(k-1)，再跳2^(k-1)
    for (let k = 1; k < this.LOG; k++) {
      for (let node = 0; node < n; node++) {
        const mid = this.anc[node][k - 1];
        this.anc[node][k] = mid === -1 ? -1 : this.anc[mid][k - 1];
      }
    }
  }

  getKthAncestor(node: number, k: number): number {
    // 用k的二進位表示分解跳躍次數
    for (let bit = 0; bit < this.LOG; bit++) {
      if ((k >> bit) & 1) {
        node = this.anc[node][bit];
        if (node === -1) return -1; // 超出根節點
      }
    }
    return node;
    // 時間複雜度：O(log k)每次查詢
  }
}

// 測試
const ta = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);
console.log(ta.getKthAncestor(3, 1)); // 1
console.log(ta.getKthAncestor(5, 2)); // 0
console.log(ta.getKthAncestor(6, 3)); // -1（超出根）

總結

本文涵蓋了進階樹演算法的核心技術：

LCA 倍增法：預處理 anc[node][k]，查詢時用二進位分解同步深度並逐步逼近 LCA，是競程中查詢最近公共祖先的標準方法
樹 DP：後序遍歷框架讓狀態從葉子往根匯總，打家劫舍 III（337）和最大路徑和（124）是最佳練習題
Euler Tour：DFS 進出時間記錄，將祖先關係轉化為區間包含，是 O(1) LCA 查詢的基礎
重鏈剖分（HLD）：重邊構成重鏈，鏈上節點在 DFS 序中連續，搭配線段樹可做路徑區間查詢（O(log² N)）
重心分治：重心樹高度 ≤ log N，是統計「所有路徑中滿足條件的對數」問題的利器

這些技術共同構成了樹結構高效處理的工具箱。初學者可先從 LCA 倍增法和基礎樹 DP（236、543、337）入手，熟練後再挑戰重鏈剖分和重心分治。

上一篇：最小生成樹 — Kruskal 與 Prim 演算法

下一篇預告：網路流（Network Flow） — 最大流（Max-Flow）、最小割（Min-Cut）與 Dinic 演算法，解鎖圖論中最強大的一類問題。

希望這篇文章能幫助你深入理解進階樹演算法的核心思路。如有任何問題或疑惑，歡迎透過 Contact 頁面與我聯繫！