Tổ tiên chung thấp nhất (LCA)

Tổ tiên chung thấp nhất (Lowest Common Ancestor, viết tắt LCA) của hai đỉnh $u,v$ trên một cây có gốc là đỉnh sâu nhất vừa là tổ tiên của $u$ vừa là tổ tiên của $v$ (quy ước mỗi đỉnh là tổ tiên của chính nó). LCA là "điểm gặp" của đường đi $u\to v$: mọi câu hỏi về đường đi trên cây (khoảng cách, tổng, max, đếm số đường phủ một cạnh...) đều quy về LCA. Leo từng bước mất $O(N)$ mỗi truy vấn; trang này trình bày các cách đưa về $O(\log N)$, $O(1)$ (online) và gần $O(1)$ (offline), rồi đi qua các ứng dụng hay gặp.

Trang cha Cây chỉ có đoạn code LCA ngắn; chi tiết cài đặt bằng nâng nhị phân nằm ở trang Binary Lifting. Trang này tập trung vào bức tranh đầy đủ: vì sao mỗi cách đúng, cách nào hợp với bài nào, và cách dùng LCA để giải bài.

Ý tưởng / Trực giác

Định nghĩa và hình dung

Treo cây ở gốc $r$. Đường đi từ $u$ lên gốc và từ $v$ lên gốc là hai "nhánh" cùng kết thúc ở $r$. Hai nhánh này trùng nhau từ một đỉnh nào đó trở lên; đỉnh trùng đầu tiên (thấp nhất) chính là $w=\text{LCA}(u,v)$. Đường đi duy nhất giữa $u$ và $v$ là:

$$u\to \text{cha}(u)\to \cdots \to w\to \cdots \to \text{cha}(v)\to v,$$

tức là "đi lên từ $u$ tới $w$, rồi đi xuống từ $w$ tới $v$". Mọi đại lượng trên đường đi vì thế tách thành hai đoạn dọc (từ một đỉnh lên tổ tiên của nó), mà đoạn dọc thì dễ xử lý bằng tổng tiền tố từ gốc hoặc nâng nhị phân.

Hai trường hợp đặc biệt cần nhớ: nếu $u$ là tổ tiên của $v$ thì $\text{LCA}(u,v)=u$; và $\text{LCA}(u,u)=u$.

Cách ngây thơ: cân độ sâu rồi leo cùng nhau

1. Nếu $u$ sâu hơn $v$, leo $u$ lên cha cho tới khi $\text{dep}[u]=\text{dep}[v]$.
2. Khi đã cùng độ sâu, nếu $u\ne v$ thì cho cả hai cùng leo lên một bước, lặp tới khi trùng nhau.

Vì sao đúng? Sau bước 1, hai đỉnh cùng độ sâu nên tổ tiên chung của chúng cũng nằm ở cùng khoảng cách phía trên cả hai. Leo đồng thời giữ nguyên tính "cùng độ sâu", và lần đầu hai con trỏ trùng nhau chính là tổ tiên chung thấp nhất. Mỗi truy vấn mất $O(\text{độ sâu})$, tệ nhất $O(N)$ trên cây dạng đường thẳng. Đủ dùng khi $N·Q$ nhỏ (vài chục triệu) hoặc khi cây được bảo đảm nông (ví dụ cây nhị phân đánh số kiểu heap có độ sâu $\approx 60$).

Nâng nhị phân (binary lifting): tóm tắt

Thay vì leo từng bước, ta lưu $\text{up}[u][k]$ = tổ tiên cách $u$ đúng $2^k$ bước. Bước 1 (cân độ sâu) thành "nhảy $d$ bước" theo biểu diễn nhị phân của $d$; bước 2 thành "nhảy cú lớn nhất mà hai đỉnh vẫn khác nhau", giảm dần $k$. Tiền xử lý $O(N\log N)$, truy vấn $O(\log N)$, và cùng bảng đó trả lời được tổ tiên thứ $k$ và gộp max/min/tổng trên đường đi. Toàn bộ trực giác, bảng chạy tay và code nằm ở trang Binary Lifting; ở đây ta chỉ dùng lại hàm lca, kth_ancestor của trang đó.

Euler tour + RMQ: truy vấn $O(1)$

Chạy DFS từ gốc và ghi lại đỉnh hiện tại mỗi khi bước vào một đỉnh và mỗi khi quay về từ một con. Dãy ghi được gọi là Euler tour (chuyến đi Euler) có đúng $2N-1$ phần tử: mỗi cạnh được đi xuống một lần và đi lên một lần, tổng $2(N-1)$ bước, cộng đỉnh xuất phát. Gọi $\text{first}[x]$ là vị trí xuất hiện đầu tiên của $x$ trong dãy.

Khẳng định. Với $\text{first}[u]\le \text{first}[v]$, đỉnh nông nhất (độ sâu nhỏ nhất) trong đoạn Euler $[\text{first}[u],\text{first}[v]]$ chính là $\text{LCA}(u,v)$.

Vì sao? Gọi $w=\text{LCA}(u,v)$. Đoạn Euler này ghi lại hành trình DFS thực sự đi từ $u$ tới $v$.

• Không đi cao hơn $w$: DFS vào $w$ trước cả $u$ lẫn $v$ và chỉ rời khỏi cây con của $w$ khi đã thăm xong toàn bộ cây con đó. Vì $v$ nằm trong cây con của $w$ và chưa được thăm tại thời điểm $\text{first}[u]$, hành trình từ $u$ tới $v$ chưa thể rời cây con của $w$. Vậy mọi đỉnh trong đoạn đều có độ sâu $\ge \text{dep}[w]$.
• Có đi qua $w$: nếu $u=w$ thì hiển nhiên. Nếu không, $u$ và $v$ nằm trong cây con của hai con khác nhau của $w$ (đó là định nghĩa của "thấp nhất"). Muốn chuyển từ cây con này sang cây con kia, DFS bắt buộc quay về $w$, và lúc đó $w$ được ghi vào dãy.

Vậy đỉnh nông nhất trong đoạn là $w$. Bài toán LCA thành bài RMQ tĩnh (min trên đoạn của mảng không đổi), và Sparse Table trả lời RMQ trong $O(1)$ sau $O(M\log M)$ tiền xử lý với $M=2N-1$. Min là phép toán "lũy đẳng" ($min(x,x)=x$) nên hai đoạn con chồng lên nhau vẫn cho kết quả đúng; đó là lý do dùng được sparse table $O(1)$. Kỹ thuật duyệt cây ghi thứ tự này được trình bày kỹ ở trang Euler Tour.

Tarjan offline: một lần DFS + DSU

Khi biết trước toàn bộ truy vấn, ta trả lời tất cả trong một lần DFS. Duy trì DSU trên các đỉnh đã thăm, với quy tắc: khi DFS thăm xong đỉnh $x$ và quay về cha $p$, gộp tập của $x$ vào tập của $p$ và ghi "đại diện tổ tiên" của tập đó là $p$.

Tại thời điểm DFS thăm xong $u$, xét một truy vấn $(u,v)$ mà $v$ đã được thăm. Gọi $a$ là tổ tiên đang mở (còn trên ngăn xếp DFS) thấp nhất của $v$. Tập DSU chứa $v$ lúc này có đại diện tổ tiên là $a$ và gồm $a$ cùng mọi cây con đã thăm xong treo dưới $a$ (mỗi nhánh thăm xong đều đã "chảy" ngược lên tới tổ tiên đang mở gần nhất). Các đỉnh đã thăm nằm trong nhánh con đang mở của $a$ (nhánh chứa $u$, nếu có) thuộc những tập khác, ứng với các tổ tiên đang mở sâu hơn. Tổ tiên đang mở của $v$ đồng thời là tổ tiên của $u$, và đỉnh thấp nhất trong số đó chính là $\text{LCA}(u,v)$. Mỗi truy vấn được ghi ở cả hai đầu, nên khi đầu thăm xong sau cùng được xử lý thì đầu kia chắc chắn đã thăm. Một truy vấn có thể được trả lời hai lần (khi đầu này là tổ tiên đang mở của đầu kia), nhưng cả hai lần đều cho cùng kết quả đúng.

Dùng DSU có nén đường và hợp theo kích thước (như code bên dưới), tổng chi phí là $O((N+Q)\alpha (N))$, gần như tuyến tính. Đổi lại, phải có đủ truy vấn trước khi chạy: đây là một dạng xử lý truy vấn offline.

Ví dụ chạy tay

Dùng chung cây sau, gốc $1$, các con duyệt theo thứ tự tăng dần:

            1              dep 0
          /   \
         2     3           dep 1
        / \     \
       4   5     6         dep 2
           |
           7               dep 3

Cách ngây thơ: LCA(7, 6)

dep[7]=3, dep[6]=2  -> 7 sâu hơn, leo 1 bước: 7 -> 5
cặp (5, 6), cùng dep=2, khác nhau -> cùng leo: 5 -> 2, 6 -> 3
cặp (2, 3), cùng dep=1, khác nhau -> cùng leo: 2 -> 1, 3 -> 1
cặp (1, 1) trùng -> LCA = 1

Euler tour + sparse table

DFS: vào 1, vào 2, vào 4, về 2, vào 5, vào 7, về 5, về 2, về 1, vào 3, vào 6, về 3, về 1. Dãy Euler dài $2·7-1=13$:

vị trí i :  0  1  2  3  4  5  6  7  8  9 10 11 12
euler[i] :  1  2  4  2  5  7  5  2  1  3  6  3  1
dep      :  0  1  2  1  2  3  2  1  0  1  2  1  0

first[]:  1->0  2->1  4->2  5->4  7->5  3->9  6->10

LCA(4, 7): đoạn $[\text{first}[4],\text{first}[7]]=[2,5]$.

i     :  2  3  4  5
euler :  4  2  5  7
dep   :  2  1  2  3
             ^ nông nhất: đỉnh 2  -> LCA(4,7) = 2

Đúng: 4 và 7 nằm ở hai nhánh khác nhau (qua 4 và qua 5) của đỉnh 2.

LCA(7, 6): đoạn $[5,10]$, dài $6$, nên $k=\lfloor {\log }_{2}6\rfloor =2$. Sparse table ghép hai khối dài $4$ chồng lên nhau:

i     :  5  6  7  8  9 10
euler :  7  5  2  1  3  6
dep   :  3  2  1  0  1  2
        [ khối st[2][5]: i=5..8 ]      -> nông nhất: 1
                 [ khối st[2][7]: i=7..10 ] -> nông nhất: 1
kết quả = đỉnh nông hơn trong {1, 1} = 1

LCA(5, 7) (5 là tổ tiên của 7): đoạn $[4,5]$ gồm đỉnh 5 (dep 2) và 7 (dep 3), nông nhất là 5. Đúng: tổ tiên của đỉnh kia chính là LCA.

Tarjan offline với hai truy vấn (4, 7) và (7, 6)

Ký hiệu {...}->a: một tập DSU và đỉnh tổ tiên đại diện của nó.

vào 1, vào 2, vào 4
xong 4 : truy vấn (4,7): 7 chưa thăm, bỏ qua
         gộp 4 vào 2          tập {2,4}->2
vào 5, vào 7
xong 7 : truy vấn (7,4): 4 đã thăm, find(4) = tập {2,4}->2  => LCA(4,7) = 2
         truy vấn (7,6): 6 chưa thăm, bỏ qua
         gộp 7 vào 5          tập {5,7}->5
xong 5 : gộp vào 2            tập {2,4,5,7}->2
xong 2 : gộp vào 1            tập {1,2,4,5,7}->1
vào 3, vào 6
xong 6 : truy vấn (6,7): 7 đã thăm, find(7) = tập {1,2,4,5,7}->1  => LCA(7,6) = 1
         gộp 6 vào 3 ...

Để ý: lúc trả lời $(7,6)$, cả nhánh của đỉnh 2 đã "chảy" lên tới 1, là tổ tiên đang mở thấp nhất của 7 và cũng là tổ tiên của 6.

Cài đặt

Quy ước chung: đỉnh đánh số $1..N$, gốc là $1$. Mọi DFS/BFS đều viết không đệ quy để không tràn ngăn xếp với cây dạng đường thẳng $N=2·{10}^5$.

C++: cách ngây thơ

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

int n, q;
vector<vector<int>> adj;
vector<int> par, dep;

// BFS from root to get parent and depth (no recursion)
void bfs(int root) {
    par.assign(n + 1, 0); dep.assign(n + 1, -1);
    queue<int> qu; qu.push(root); dep[root] = 0;
    while (!qu.empty()) {
        int u = qu.front(); qu.pop();
        for (int v : adj[u]) if (dep[v] == -1) {
            dep[v] = dep[u] + 1; par[v] = u; qu.push(v);
        }
    }
}

int lca_naive(int u, int v) {
    while (dep[u] > dep[v]) u = par[u];          // lift the deeper one
    while (dep[v] > dep[u]) v = par[v];
    while (u != v) { u = par[u]; v = par[v]; }   // climb together
    return u;
}

int main() {
    cin >> n >> q;
    adj.assign(n + 1, {});
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    bfs(1);
    while (q--) { int u, v; cin >> u >> v; cout << lca_naive(u, v) << '\n'; }
}

C++: Euler tour + sparse table, truy vấn $O(1)$

Sparse table lưu trực tiếp đỉnh nông nhất của mỗi khối (so sánh bằng dep), nên kết quả truy vấn là đỉnh LCA luôn, không cần mảng chỉ số phụ.

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

// LCA via Euler tour (2n-1 entries) + sparse table on depth.
// Build O(n log n), query O(1). Vertices 1..n.
struct EulerLCA {
    int n, LOG;
    vector<vector<int>> adj;
    vector<int> dep, first, euler;   // euler: visit order, size 2n-1
    vector<int> lg;
    vector<vector<int>> st;          // st[k][i]: shallowest vertex in euler[i .. i+2^k-1]

    EulerLCA(int n) : n(n), adj(n + 1), dep(n + 1), first(n + 1) {}
    void add_edge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }

    int shallower(int a, int b) const { return dep[a] < dep[b] ? a : b; }

    void build(int root = 1) {
        euler.reserve(2 * n - 1);
        // iterative DFS: it[u] = index of the next neighbor to try
        vector<int> par(n + 1, 0), it(n + 1, 0);
        vector<int> stk = {root};
        dep[root] = 0;
        first[root] = 0;
        euler.push_back(root);
        while (!stk.empty()) {
            int u = stk.back();
            if (it[u] < (int)adj[u].size()) {
                int v = adj[u][it[u]++];
                if (v == par[u]) continue;
                par[v] = u; dep[v] = dep[u] + 1;
                first[v] = euler.size();
                euler.push_back(v);                             // enter v
                stk.push_back(v);
            } else {
                stk.pop_back();
                if (!stk.empty()) euler.push_back(stk.back());  // back to parent
            }
        }
        int m = euler.size();
        lg.assign(m + 1, 0);
        for (int i = 2; i <= m; i++) lg[i] = lg[i / 2] + 1;
        LOG = lg[m] + 1;
        st.assign(LOG, vector<int>(m));
        st[0] = euler;
        for (int k = 1; k < LOG; k++)
            for (int i = 0; i + (1 << k) <= m; i++)
                st[k][i] = shallower(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
    }

    int lca(int u, int v) const {
        int l = first[u], r = first[v];
        if (l > r) swap(l, r);
        int k = lg[r - l + 1];
        return shallower(st[k][l], st[k][r - (1 << k) + 1]);
    }
    int dist(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    EulerLCA T(n);
    for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; T.add_edge(u, v); }
    T.build(1);
    while (q--) {
        int u, v; cin >> u >> v;
        cout << T.lca(u, v) << '\n';
    }
}

Python: Euler tour + sparse table

Mỗi tầng của sparse table dựng bằng một list comprehension trên zip, nhanh hơn nhiều so với hai vòng for lồng nhau (khoảng 1 giây cho $N=Q=2·{10}^5$).

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    adj = [[] for _ in range(n + 1)]
    pos = 2
    for _ in range(n - 1):
        u, v = int(data[pos]), int(data[pos + 1]); pos += 2
        adj[u].append(v); adj[v].append(u)

    # iterative DFS building the Euler tour (2n-1 entries)
    dep = [0] * (n + 1)
    first = [0] * (n + 1)
    par = [0] * (n + 1)
    it = [0] * (n + 1)
    euler = [1]
    stack = [1]
    while stack:
        u = stack[-1]
        if it[u] < len(adj[u]):
            v = adj[u][it[u]]; it[u] += 1
            if v == par[u]:
                continue
            par[v] = u; dep[v] = dep[u] + 1
            first[v] = len(euler)
            euler.append(v)
            stack.append(v)
        else:
            stack.pop()
            if stack:
                euler.append(stack[-1])      # back to parent

    # sparse table of "shallowest vertex" over euler
    m = len(euler)
    table = [euler]
    k = 1
    while (1 << k) <= m:
        prev, half = table[-1], 1 << (k - 1)
        table.append([a if dep[a] < dep[b] else b
                      for a, b in zip(prev, prev[half:])])
        k += 1

    out = []
    for _ in range(q):
        u, v = int(data[pos]), int(data[pos + 1]); pos += 2
        l, r = first[u], first[v]
        if l > r:
            l, r = r, l
        k = (r - l + 1).bit_length() - 1
        a, b = table[k][l], table[k][r - (1 << k) + 1]
        out.append(a if dep[a] < dep[b] else b)
    print("\n".join(map(str, out)))

main()

C++: Tarjan offline

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

// Offline LCA (Tarjan): one DFS + DSU (path halving + union by size),
// O((n + q) * alpha(n)).
int n, q;
vector<vector<int>> adj;
vector<vector<pair<int,int>>> qs;    // qs[u] = {(other vertex, query id)}
vector<int> dsu, sz, anc, ans;    // anc[root of set] = its open ancestor
vector<char> visited;

int find(int x) {                     // path halving
    while (dsu[x] != x) x = dsu[x] = dsu[dsu[x]];
    return x;
}

void tarjan(int root) {
    // iterative DFS; it[u] = index of the next neighbor to try
    vector<int> par(n + 1, 0), it(n + 1, 0), stk = {root};
    while (!stk.empty()) {
        int u = stk.back();
        if (it[u] == 0) {             // first time we see u
            visited[u] = 1;
            anc[u] = u;
        }
        if (it[u] < (int)adj[u].size()) {
            int v = adj[u][it[u]++];
            if (v != par[u]) { par[v] = u; stk.push_back(v); }
            continue;
        }
        // u is finished: answer queries whose other end is already visited
        for (auto [v, id] : qs[u])
            if (visited[v]) ans[id] = anc[find(v)];
        stk.pop_back();
        if (!stk.empty()) {           // merge u's subtree into its parent
            int p = stk.back();
            int a = find(u), b = find(p);
            if (sz[a] > sz[b]) swap(a, b);   // union by size
            dsu[a] = b; sz[b] += sz[a];
            anc[b] = p;                      // merged set now hangs at p
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> q;
    adj.assign(n + 1, {}); qs.assign(n + 1, {});
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    ans.assign(q, 0);
    for (int i = 0; i < q; i++) {
        int u, v; cin >> u >> v;
        qs[u].push_back({v, i});
        qs[v].push_back({u, i});      // store at both ends
    }
    dsu.resize(n + 1); iota(dsu.begin(), dsu.end(), 0); sz.assign(n + 1, 1);
    anc.assign(n + 1, 0); visited.assign(n + 1, 0);
    tarjan(1);
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

Ghi chú: truy vấn $(u,u)$ vẫn đúng, vì lúc $u$ thăm xong thì $u$ đã thăm và $\text{anc}[\text{find}(u)]=u$.

Ứng dụng của LCA

Các hàm dưới đây giả sử đã có dep[], lca(u, v) và kth_ancestor(u, k) (tổ tiên cách $u$ đúng $k$ bước, xem Binary Lifting). Ký hiệu $w=\text{LCA}(u,v)$.

1. Khoảng cách hai đỉnh

$$\text{dist}(u,v)=\text{dep}[u]+\text{dep}[v]-2\text{dep}[w].$$

Đoạn $u\to w$ dài $\text{dep}[u]-\text{dep}[w]$, đoạn $w\to v$ dài $\text{dep}[v]-\text{dep}[w]$. Nếu cạnh có trọng số, thay dep bằng distRoot (tổng trọng số từ gốc, kiểu long long).

2. Đỉnh $x$ có nằm trên đường đi $a\to b$ không?

$$x\in \text{path}(a,b)⟺\text{dist}(a,x)+\text{dist}(x,b)=\text{dist}(a,b).$$

Đường đi trên cây là duy nhất, nên đi $a\to x\to b$ chỉ dài bằng $a\to b$ khi $x$ nằm ngay trên đó. Một cách tương đương dùng thời điểm vào/ra tin/tout (xem Euler Tour): $x$ nằm trên đường đi khi và chỉ khi $x$ là tổ tiên của $a$ hoặc của $b$, và $\text{LCA}(a,b)$ là tổ tiên của $x$.

3. Đỉnh thứ $k$ trên đường đi $u\to v$

Đánh số các đỉnh trên đường từ $0$ (là $u$) tới $\text{dist}(u,v)$ (là $v$). Gọi $d_u=\text{dep}[u]-\text{dep}[w]$, $d_v=\text{dep}[v]-\text{dep}[w]$:

• nếu $k\le d_u$: đỉnh cần tìm còn ở nửa đi lên, là tổ tiên thứ $k$ của $u$;
• ngược lại: nó ở nửa đi xuống, cách $v$ đúng $d_u+d_v-k$ bước về phía gốc.

4. Tổng trên đường đi bằng tổng tiền tố gốc-đỉnh

Đặt $f(x)$ = tổng giá trị các đỉnh trên đường từ gốc tới $x$ (tính một lần bằng DFS/BFS: $f(x)=f(\text{cha}(x))+\text{val}[x]$). Khi đó

$$\text{sum}(u,v)=f(u)+f(v)-2f(w)+\text{val}[w].$$

$f(u)+f(v)$ đếm đoạn từ gốc tới $w$ hai lần, nên trừ $2f(w)$; nhưng như vậy trừ luôn cả $\text{val}[w]$ hai lần trong khi $w$ thuộc đường đi, nên cộng lại một lần. Nếu giá trị nằm trên cạnh (gán cạnh $(x,\text{cha}(x))$ cho đỉnh $x$) thì công thức gọn hơn: $f(u)+f(v)-2f(w)$, vì cạnh "của" $w$ không nằm trên đường đi. Công thức chỉ dùng được cho phép toán có phép ngược (cộng, XOR); với max/min phải dùng bảng gộp của binary lifting hoặc HLD.

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

bool on_path(int x, int a, int b) {           // is x on path a..b ?
    return dist(a, x) + dist(x, b) == dist(a, b);
}

int kth_on_path(int u, int v, int k) {        // k = 0 gives u, k = dist gives v
    int w = lca(u, v);
    int du = dep[u] - dep[w], dv = dep[v] - dep[w];
    if (k <= du) return kth_ancestor(u, k);    // still on the u -> w half
    return kth_ancestor(v, du + dv - k);       // on the w -> v half
}

// f[x] = val[root] + ... + val[x], computed once in BFS order
long long path_sum(int u, int v) {            // sum of vertex values on path
    int w = lca(u, v);
    return f[u] + f[v] - 2 * f[w] + val[w];    // w was subtracted twice
}

5. Đếm số đường đi phủ mỗi cạnh / mỗi đỉnh: hiệu trên cây

Bài toán: cho $M$ đường đi $(a_i,b_i)$, hỏi mỗi cạnh (hoặc mỗi đỉnh) bị bao nhiêu đường đi đi qua. Làm từng đường một mất $O(NM)$. Hiệu trên cây (difference on tree) là phiên bản trên cây của mảng hiệu: đánh dấu $O(1)$ ô cho mỗi đường, rồi cộng dồn từ lá lên gốc một lần.

Quy ước cạnh $(x,\text{cha}(x))$ được lưu tại đỉnh con $x$. Sau khi cộng dồn, giá trị tại $x$ bằng tổng các dấu trong cây con của $x$.

• Đếm theo cạnh: $+1$ tại $a$, $+1$ tại $b$, $-2$ tại $w$. Với cạnh trên đoạn $a\to w$, cây con phía dưới chứa $a$ nhưng không chứa $w$: tổng $=1$. Cạnh phía trên $w$: cây con chứa cả $a,b,w$, tổng $1+1-2=0$. Cạnh ngoài đường đi: không chứa dấu nào, hoặc chứa đủ cả bộ nên tổng $0$.
• Đếm theo đỉnh: $+1$ tại $a$, $+1$ tại $b$, $-1$ tại $w$, $-1$ tại $\text{cha}(w)$ (nếu $w$ không phải gốc). Đỉnh $w$ nhận $1+1-1=1$ (được đếm đúng một lần), còn từ $\text{cha}(w)$ trở lên tổng về $0$.

Chạy tay trên cây ví dụ với hai đường $(4,7)$ (LCA $=2$) và $(7,6)$ (LCA $=1$), đếm theo cạnh:

dấu ban đầu:  +1@4 +1@7 -2@2      (đường 4-7)
              +1@7 +1@6 -2@1      (đường 7-6)
d[] trước cộng dồn:  1:-2  2:-2  3:0  4:+1  5:0  6:+1  7:+2

cộng dồn từ lá lên (d[x] += tổng các con):
  7: 2          -> cạnh 7-5 bị phủ 2 lần
  5: 0+2 = 2    -> cạnh 5-2 bị phủ 2 lần
  4: 1          -> cạnh 4-2 bị phủ 1 lần
  2: -2+1+2 = 1 -> cạnh 2-1 bị phủ 1 lần (chỉ đường 7-6)
  6: 1          -> cạnh 6-3: 1 lần
  3: 0+1 = 1    -> cạnh 3-1: 1 lần
  1: -2+1+1 = 0 (gốc, không có cạnh lên)

Chương trình đầy đủ (in số đường đi qua mỗi đỉnh, rồi số đường đi qua mỗi cạnh $(v,\text{cha}(v))$). Thứ tự BFS bảo đảm cha đứng trước con, nên duyệt ngược thứ tự BFS là cộng dồn từ lá lên mà không cần đệ quy:

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

// Difference on tree: for m paths (a, b), count how many paths pass
// through each vertex (cntV[x]) and through each edge (cntE[x] = edge x - par[x]).
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    // BFS order: parents appear before children; build binary lifting on the fly
    // LOG = 18 covers jumps up to 2^18 - 1 steps: safe for n <= 262144.
    // Increase it (e.g. 20 for n <= 10^6) for larger trees.
    const int LOG = 18;
    vector<array<int, LOG>> up(n + 1);
    vector<int> dep(n + 1, -1), order = {1};
    up[1].fill(1); dep[1] = 0;
    for (size_t i = 0; i < order.size(); i++) {
        int u = order[i];
        for (int v : adj[u]) if (dep[v] == -1) {
            dep[v] = dep[u] + 1;
            up[v][0] = u;
            for (int k = 1; k < LOG; k++) up[v][k] = up[up[v][k - 1]][k - 1];
            order.push_back(v);
        }
    }
    auto lca = [&](int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        for (int k = LOG - 1; k >= 0; k--)
            if (dep[u] - (1 << k) >= dep[v]) u = up[u][k];
        if (u == v) return u;
        for (int k = LOG - 1; k >= 0; k--)
            if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; }
        return up[u][0];
    };

    vector<long long> cntV(n + 1, 0), cntE(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        int w = lca(a, b);
        // vertex version: +1 a, +1 b, -1 w, -1 parent(w)
        cntV[a]++; cntV[b]++; cntV[w]--;
        if (w != 1) cntV[up[w][0]]--;
        // edge version: +1 a, +1 b, -2 w
        cntE[a]++; cntE[b]++; cntE[w] -= 2;
    }
    // accumulate from leaves up: reverse BFS order
    for (int i = n - 1; i >= 1; i--) {
        int u = order[i], p = up[u][0];
        cntV[p] += cntV[u];
        cntE[p] += cntE[u];
    }
    for (int v = 1; v <= n; v++) cout << cntV[v] << " \n"[v == n];
    for (int v = 2; v <= n; v++) cout << cntE[v] << " \n"[v == n];   // edge (v, parent)
}

Mẹo "hiệu trên cây" còn dùng được với cộng một giá trị $x$ lên mọi đỉnh/cạnh của đường đi (thay $+1$ bằng $+x$), với điều kiện chỉ hỏi kết quả sau khi mọi cập nhật xong. Nếu cập nhật và truy vấn đan xen, cần Heavy-Light Decomposition hoặc Fenwick trên Euler tour.

Độ phức tạp

Lý giải từng dòng:

• Ngây thơ: mỗi vòng while đưa một con trỏ lên một tầng, tổng số bước không quá $\text{dep}[u]+\text{dep}[v]$.
• Euler + sparse table: dãy Euler có $M=2N-1$ phần tử; sparse table có $\lfloor {\log }_{2}M\rfloor +1$ tầng, mỗi tầng $\le M$ ô tính $O(1)$, nên tiền xử lý và bộ nhớ $O(N\log N)$. Truy vấn chỉ là hai lần đọc bảng và một phép so sánh. Với $N=2·{10}^5$: $M\approx 4·{10}^5$, $19$ tầng, khoảng $7,6·{10}^6$ số int $\approx 30$ MB.
• Tarjan: DFS thăm mỗi đỉnh và cạnh $O(1)$ lần; mỗi truy vấn được xét hai lần (ở hai đầu), mỗi lần một phép find; có $N-1$ phép hợp. Code mẫu dùng chia đôi đường (một dạng nén đường) kết hợp hợp theo kích thước, nên tổng là $O((N+Q)\alpha (N))$. Nếu bỏ hợp theo kích thước (chỉ nén đường), cận lý thuyết là $O((N+Q)\log N)$ khấu trừ, thực tế vẫn chạy rất nhanh.
• Hiệu trên cây: $M$ lần gọi LCA cộng một lần cộng dồn $O(N)$, tổng $O(N\log N+M\log N)$ với binary lifting.

⚠️ Lỗi thường gặp

• Tràn ngăn xếp vì DFS đệ quy. Triệu chứng: Runtime Error trên test cây đường thẳng $N=2·{10}^5$ dù test ngẫu nhiên chạy đúng. Cách tránh: viết DFS bằng ngăn xếp tự quản (như code ở trên) hoặc dùng thứ tự BFS khi chỉ cần cha/độ sâu.
• Mảng Euler khai báo cỡ $N$ thay vì $2N-1$. Dãy Euler dạng "vào + quay về" dài gần gấp đôi số đỉnh. Khai báo euler[MAXN] sẽ ghi tràn mảng, sai âm thầm hoặc lỗi bộ nhớ. Sparse table cũng phải dựng trên độ dài $2N-1$, và LOG tính theo độ dài đó.
• Lấy min độ sâu nhưng quên trả về đỉnh. Nếu sparse table chỉ lưu dep nhỏ nhất thì ta biết độ sâu của LCA chứ không biết LCA là đỉnh nào. Lưu đỉnh (hoặc chỉ số trong dãy Euler) và so sánh theo dep, như hàm shallower trong code.
• Lẫn chỉ số giữa hai kiểu dãy. Đoạn truy vấn phải nằm giữa hai vị trí trong chính dãy Euler $2N-1$ phần tử (dùng first[] là chuẩn). Nếu lấy nhầm tin[] của thứ tự DFS chỉ ghi khi vào (dãy dài $N$) để tra trên bảng dựng từ dãy Euler, chỉ số lệch và kết quả sai âm thầm. Nhớ hoán đổi để $l\le r$ trước khi tra bảng.
• Công thức tổng đường đi quên cộng lại $\text{val}[w]$. $f(u)+f(v)-2f(w)$ bỏ mất giá trị tại LCA khi giá trị nằm trên đỉnh. Ngược lại, khi giá trị nằm trên cạnh thì không được cộng. Kiểm tra nhanh bằng truy vấn $(u,u)$: kết quả phải là $\text{val}[u]$ (đỉnh) hoặc $0$ (cạnh).
• Hiệu trên cây theo đỉnh quên trừ ở $\text{cha}(w)$. Chỉ đặt $-2$ tại $w$ (như bản theo cạnh) thì đỉnh $w$ bị đếm $0$ lần. Bản theo đỉnh cần $-1$ tại $w$ và $-1$ tại cha của $w$; khi $w$ là gốc thì bỏ dấu thứ hai.
• Cộng dồn sai thứ tự. Phải cộng từ lá lên (hậu thứ tự DFS hoặc ngược thứ tự BFS). Duyệt theo chỉ số đỉnh $1..N$ chỉ đúng khi đề bảo đảm cha có chỉ số nhỏ hơn con.
• Tarjan: quên lưu truy vấn ở cả hai đầu hoặc quên đánh dấu đã thăm. Nếu chỉ lưu tại $u$, khi $u$ thăm xong trước $v$ thì truy vấn bị bỏ qua mãi mãi (đáp án $0$). Phải lưu tại cả $u$ và $v$, và chỉ trả lời khi đầu kia đã thăm.
• Tràn số khi cạnh có trọng số. dep đếm cạnh thì int đủ, nhưng tổng trọng số từ gốc có thể tới $2·{10}^5·{10}^9$: dùng long long cho distRoot và f.
• Cây không cho gốc hoặc là rừng. LCA phụ thuộc gốc; khoảng cách thì không. Nếu đồ thị là rừng, phải DFS từ mọi thành phần và kiểm tra hai đỉnh cùng thành phần trước khi hỏi LCA (nhiều bài có đáp án $-1$ cho trường hợp khác thành phần).

Biến thể / Mở rộng

• Sparse table cỡ $N$ trên thứ tự DFS. Thay dãy Euler $2N-1$ phần tử bằng thứ tự vào DFS order[] (mỗi đỉnh một lần, tin[u] là vị trí). Với $u\ne v$ và $\text{tin}[u]<\text{tin}[v]$: LCA là cha của đỉnh nông nhất trong order[tin[u]+1 .. tin[v]]. Bộ nhớ giảm một nửa, vẫn truy vấn $O(1)$.
• LCA với gốc thay đổi. Nếu hỏi "LCA của $u,v$ khi treo cây ở $r$", đáp án là đỉnh sâu nhất (theo gốc cố định) trong ba đỉnh $\text{LCA}(u,v)$, $\text{LCA}(u,r)$, $\text{LCA}(v,r)$.
• LCA của cả một tập đỉnh. LCA của tập $S$ bằng LCA của hai đỉnh có tin nhỏ nhất và lớn nhất trong $S$. Đây cũng là nền của Virtual Tree, nơi chỉ cần LCA của các cặp liền kề theo tin.
• Max/min trên đường đi. Không có phép ngược nên không dùng tổng tiền tố được; dùng bảng gộp của Binary Lifting (đường đi tĩnh) hoặc HLD + segment tree (có cập nhật).
• Cây Kruskal (Kruskal reconstruction tree). Dựng cây mà mỗi lần hợp hai thành phần tạo một đỉnh mới mang trọng số cạnh; các cạnh phải được xét và hợp theo trọng số tăng dần. Khi đó, xét mọi đường đi $u\to v$ trong đồ thị gốc, giá trị nhỏ nhất có thể của cạnh lớn nhất trên đường (đường minimax, bottleneck) bằng trọng số của $\text{LCA}(u,v)$ trên cây mới. Muốn giá trị lớn nhất có thể của cạnh nhỏ nhất thì hợp theo trọng số giảm dần. Biến bài đồ thị thành bài LCA.
• Cây động (thêm/xoá cạnh): các cách trên không còn hợp; xem Link-Cut Tree.

Bài tập luyện

Luyện kỹ thuật

• Lorenzo Von Matterhorn (lorenzo) (Nâng cao) cây nhị phân vô hạn đánh số kiểu heap nên độ sâu chỉ khoảng $60$: cách ngây thơ "đỉnh lớn hơn thì leo lên $x/2$" là đủ, mỗi cạnh lưu trong map theo đỉnh con.
• Tổ tiên chung thấp nhất (LCA) (compqry2) (Nâng cao) LCA thuần tuý với $n,q\le 2·{10}^5$: cài binary lifting hoặc Euler tour + sparse table và so sánh tốc độ.
• Truy vấn khoảng cách (distqry) (Nâng cao) áp dụng trực tiếp $\text{dist}=\text{dep}[u]+\text{dep}[v]-2\text{dep}[w]$; hợp để cài bản Euler tour truy vấn $O(1)$.
• Đếm đường đi qua đỉnh (cntpath) (Nâng cao) bài mẫu của hiệu trên cây theo đỉnh: $+1$ ở hai đầu, $-1$ ở LCA và ở cha của LCA, rồi cộng dồn từ lá lên.
• Hối lộ (bribes) (Kỳ cựu) hiệu trên cây theo cạnh có hướng: tách mỗi chặng thành nửa đi lên $s\to w$ và nửa đi xuống $w\to t$, dùng hai mảng hiệu riêng, rồi mỗi cạnh một chiều bị đi ngược $c$ lần tốn $2^c-1$.

Đề VOI

• Nâng cấp mạng (voi11_ugnet) (Nâng cao) VOI 2011: hãy tự hỏi thông lượng tốt nhất giữa hai máy nằm trên cây khung nào, rồi suy ra mỗi cáp cần so với đại lượng gì trên cây đó. LCA + binary lifting (gộp thông tin trên đường đi trong cây) là một cách giải; lời giải chính thức leo trực tiếp trên cây DSU hợp theo kích thước.
• Người giao hàng (voi25_ship) (Nâng cao) VOI 2025: mỗi nhiệm vụ cần giá trị lớn nhất trên đường $U_i\to V_i$, tức là max trên hai đoạn dọc gặp nhau ở LCA (đừng quên chính đỉnh LCA). Sau đó hãy nghĩ xem giữa các nhiệm vụ chỉ cần nhớ thông tin gì.
• Chia nhóm (voi21_teamup) (Chuyên gia) VOI 2021: đồ thị hàm gồm chu trình với các cây treo; LCA chỉ là một phần của lời giải, dùng khi cạnh thêm vào nối hai đỉnh cùng một cây treo để lấy độ dài và trọng số nhỏ nhất của chu trình mới $u\to \text{LCA}\to v$.