Wiki › Cấu trúc dữ liệu › Cây › Virtual Tree

Virtual Tree

huunguyen Updated Tháng sáu 2, 2026

Virtual Tree (cây ảo, còn gọi auxiliary tree) là kỹ thuật nén một cây $N$ đỉnh thành một cây con nhỏ chỉ chứa tập đỉnh quan trọng (key vertices) và các tổ tiên chung thấp nhất (LCA) cần thiết của chúng. Nhờ đó, một truy vấn chỉ liên quan tới $K$ đỉnh có thể được xử lý trong $O (K \log K)$ thay vì $O (N)$ — cực kỳ hữu ích khi có nhiều truy vấn với tổng $\sum K ≪ N \cdot Q$ .

Bài toán điển hình: cho cây $N$ đỉnh và $Q$ truy vấn, mỗi truy vấn cho một tập $K$ đỉnh đặc biệt; cần tính một đại lượng (DP, Steiner tree, khoảng cách...) chỉ phụ thuộc vào quan hệ giữa các đỉnh đặc biệt đó. Nếu chạy DP trên toàn cây mỗi truy vấn thì tốn $O (N Q)$ , thường quá lớn. Virtual tree cho phép mỗi truy vấn chỉ làm việc trên $O (K)$ đỉnh, đưa tổng về $O (\sum K \log K)$ khi đề bảo đảm $\sum K \leq N$ (hoặc $\leq 10^{6}$ ).

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

Vì sao chỉ cần giữ lại các đỉnh quan trọng và LCA của chúng?

Trên cây, mọi "đường đi" hay "cấu trúc" liên kết tập $S$ các đỉnh quan trọng đều đi qua các điểm rẽ nhánh. Một điểm rẽ nhánh chỉ xuất hiện ở chỗ hai nhánh chứa đỉnh quan trọng gặp nhau, tức là tại một LCA của hai đỉnh quan trọng nào đó. Mọi đỉnh khác của cây gốc chỉ nằm trên một đoạn đường thẳng (không rẽ), nên ta có thể "nén" cả đoạn đó thành một cạnh có trọng số trong cây ảo (trọng số = khoảng cách thật) mà không mất thông tin.

Hai quan sát then chốt:

Sắp theo Euler tour (thời điểm vào DFS tin[]) thì chỉ cần xét LCA của các cặp LIÊN TIẾP. Nếu $u_{1}, u_{2}, \dots, u_{m}$ là tập đỉnh đã sắp tăng theo tin, thì tập tất cả các LCA "có ý nghĩa" của mọi cặp đúng bằng ${l c a (u_{i}, u_{i + 1}) : 1 \leq i < m}$ . Lý do: LCA của hai đỉnh bất kỳ luôn nằm trong dãy LCA của các cặp liên tiếp giữa chúng (LCA có depth nhỏ nhất). Đây là điều giúp ta không phải xét $O (K^{2})$ cặp mà chỉ $O (K)$ .
Số đỉnh cây ảo $\leq 2 K - 1$ . Mỗi đỉnh thêm vào là một LCA của hai đỉnh quan trọng; số điểm rẽ nhánh phân biệt không vượt quá $K - 1$ . Vậy cây ảo nhỏ tuyến tính theo $K$ .

Cách xây dựng dùng stack mô phỏng việc đi dọc "biên phải" của cây trong thứ tự DFS: stack luôn giữ chuỗi tổ tiên hiện tại từ gốc ảo xuống. Khi thêm đỉnh mới $u$ , ta tính $l = l c a (u, đỉnh đỉnh stack)$ ; mọi đỉnh trong stack sâu hơn $l$ đã "đóng nhánh" nên được nối cạnh và pop ra, sau đó đẩy $l$ (nếu cần) rồi đẩy $u$ .

Ví dụ chạy tay

Cây gốc (gốc = 1), depth ghi bên cạnh:

            1 (d=0)
           / \
       (d=1)2  3 (d=1)
         / \
   (d=2)4   5 (d=2)
       /
 (d=3)6

Giả sử DFS thăm con theo thứ tự tăng dần số hiệu, ta được tin:

đỉnh:  1  2  4  6  5  3
tin :  0  1  2  3  4  5

Tập đỉnh quan trọng: $S = {6, 5, 3}$ .

Bước 1 — sắp theo tin: tin[6]=3, tin[5]=4, tin[3]=5 → đã đúng thứ tự [6, 5, 3].

Bước 2 — thêm LCA cặp liên tiếp:

$l c a (6, 5) = 2$
$l c a (5, 3) = 1$

Gộp lại: ${6, 5, 3, 2, 1}$ . Sắp theo tin: 1(0), 2(1), 6(3), 5(4), 3(5) → danh sách [1, 2, 6, 5, 3].

Bước 3 — dựng cây bằng stack. Ký hiệu stack từ đáy→đỉnh, ^ chỉ đỉnh stack.

xét 1: stack rỗng -> push 1            stack: [1]
                                              ^
xét 2: l = lca(2,1) = 1 = top -> push 2 stack: [1, 2]
                                                  ^
xét 6: l = lca(6,2) = 2 = top -> push 6 stack: [1, 2, 6]
                                                     ^
xét 5: l = lca(5,6) = 2 != top(6)
        depth[6]=3 > depth[2]=2 -> pop 6, nối cạnh (2,6)
        top giờ là 2 = l -> dừng pop, push 5
        edges: {(2,6)}                  stack: [1, 2, 5]
                                                     ^
xét 3: l = lca(3,5) = 1 != top(5)
        depth[5]=2 > depth[1]=0 -> pop 5, nối cạnh (2,5)
        depth[2]=1 > depth[1]=0 -> pop 2, nối cạnh (1,2)
        top giờ là 1 = l -> dừng pop, push 3
        edges: {(2,6),(2,5),(1,2)}      stack: [1, 3]
                                                    ^
hết đỉnh: xả stack: pop 3 nối (1,3)
        edges: {(2,6),(2,5),(1,2),(1,3)}

Cây ảo thu được (5 đỉnh, đúng $\leq 2 \cdot 3 - 1 = 5$ ):

Đỉnh 4 (không quan trọng, không là LCA) đã bị loại. Cạnh ảo $(1, 2)$ thực ra "che" đoạn $1 - 2$ dài 1; nếu cần trọng số ta gán $d i s t (1, 2) = depth [2] - depth [1] = 1$ .

Cài đặt

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

const int MAXN = 2e5 + 5;
const int LOG  = 18;

vector<int> adj[MAXN];
int tin[MAXN], dep[MAXN], up[MAXN][LOG];
int timer_val = 0;

// DFS tính tin[], depth[], bảng nhảy nhị phân up[][]
void dfs(int u, int p) {
    tin[u] = timer_val++;
    up[u][0] = p;
    for (int j = 1; j < LOG; j++)
        up[u][j] = up[ up[u][j-1] ][j-1];
    for (int v : adj[u])
        if (v != p) { dep[v] = dep[u] + 1; dfs(v, u); }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int j = 0; j < LOG; j++)
        if (d >> j & 1) u = up[u][j];
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--)
        if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; }
    return up[u][0];
}

// Danh sách kề của CÂY ẢO; nhớ xoá sạch sau mỗi truy vấn
vector<int> vadj[MAXN];

// Xây virtual tree từ tập key[], trả về GỐC của cây ảo.
// Sau khi gọi, vadj[] chứa các cạnh có hướng (cha -> con).
int build_virtual_tree(vector<int> key) {
    // 1) sắp theo Euler tour và khử trùng lặp
    sort(key.begin(), key.end(),
         [](int a, int b){ return tin[a] < tin[b]; });
    key.erase(unique(key.begin(), key.end()), key.end());

    // 2) bổ sung LCA của các cặp LIÊN TIẾP (chỉ O(K) cặp là đủ)
    int m = key.size();
    for (int i = 0; i + 1 < m; i++)
        key.push_back(lca(key[i], key[i + 1]));

    // sắp + khử trùng lần nữa sau khi đã thêm LCA
    sort(key.begin(), key.end(),
         [](int a, int b){ return tin[a] < tin[b]; });
    key.erase(unique(key.begin(), key.end()), key.end());

    // 3) dựng cây bằng stack mô phỏng biên phải DFS
    for (int u : key) vadj[u].clear();   // dọn trước khi dùng
    stack<int> st;
    int root = key[0];                   // đỉnh có tin nhỏ nhất là gốc ảo
    for (int u : key) {
        if (st.empty()) { st.push(u); continue; }
        int l = lca(u, st.top());
        // pop mọi đỉnh sâu hơn l và nối cạnh
        while (st.size() >= 2 && dep[ st.top() ] > dep[l]) {
            int child = st.top(); st.pop();
            int par = (dep[st.top()] >= dep[l]) ? st.top() : l;
            vadj[par].push_back(child);
        }
        if (st.top() != l) {            // l chưa có trong stack
            vadj[l].push_back(st.top());
            st.pop();
            st.push(l);
            root = (tin[l] < tin[root]) ? l : root;
        }
        st.push(u);
    }
    // xả phần còn lại
    while (st.size() >= 2) {
        int child = st.top(); st.pop();
        vadj[st.top()].push_back(child);
    }
    return root;
}

Ví dụ áp dụng — tổng độ dài Steiner tree nối tập đỉnh quan trọng (tổng độ dài cây con nhỏ nhất bao phủ chúng) có thể tính trực tiếp không cần dựng cây ảo, nhưng minh hoạ rõ vai trò LCA:

// dist[u] = khoảng cách (số cạnh hoặc trọng số) từ gốc tới u
long long steiner_len(vector<int> key, vector<long long>& dist) {
    sort(key.begin(), key.end(),
         [](int a, int b){ return tin[a] < tin[b]; });
    key.erase(unique(key.begin(), key.end()), key.end());
    long long ans = 0;
    int m = key.size();
    // cộng dist của cạnh "vòng quanh" theo thứ tự Euler rồi chia 2
    for (int i = 0; i < m; i++) {
        int u = key[i], v = key[(i + 1) % m];
        ans += dist[u] + dist[v] - 2 * dist[ lca(u, v) ]; // = dist(u,v)
    }
    return ans / 2;   // mỗi cạnh được đếm đúng 2 lần
}

Độ phức tạp

Tiền xử lý: DFS + bảng nhảy nhị phân $O (N \log N)$ thời gian, $O (N \log N)$ bộ nhớ cho mảng up[][].
Mỗi LCA: $O (\log N)$ với binary lifting (hoặc $O (1)$ nếu dùng Euler + Sparse Table).
Xây một virtual tree với $K$ đỉnh quan trọng: chi phí bị chi phối bởi hai lần sort ( $O (K \log K)$ ) và $O (K)$ lần gọi LCA ( $O (K \log N)$ ). Vòng stack chỉ $O (K)$ vì mỗi đỉnh được push/pop đúng một lần. Vậy mỗi truy vấn $O (K \log K + K \log N)$ .
Tổng cho $Q$ truy vấn: $O (\sum K_{i} (\log K_{i} + \log N))$ . Khi đề bảo đảm $\sum K_{i} \leq N$ , tổng là $O (N \log N)$ — thay vì $O (N Q)$ của cách chạy DP trên toàn cây.
Bộ nhớ: $O (N \log N)$ cho bảng LCA, cộng $O (K)$ tạm thời cho mỗi cây ảo (phải dọn lại vadj[] sau mỗi truy vấn, không clear toàn bộ $N$ đỉnh kẻo mất tính $O (K)$ ).

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

Clear toàn bộ vadj[1..N] mỗi truy vấn → TLE. Việc này biến mỗi truy vấn thành $O (N)$ , tổng $O (N Q)$ , đánh mất toàn bộ lợi ích của virtual tree. Chỉ được xoá đúng các đỉnh nằm trong cây ảo lần này (clear khi push, hoặc lưu danh sách đỉnh đã dùng để clear lại).
Quên thêm gốc / LCA chung của cả tập. Nếu chỉ thêm LCA của các cặp liên tiếp mà không sắp + khử trùng lần nữa, gốc thật của cây ảo (LCA của toàn bộ tập) có thể bị thiếu, làm cây ảo rời rạc (rừng). Sau khi push các LCA phải sort lại theo tin rồi unique.
Dùng depth để phân biệt thay vì tin khi sắp xếp. Thứ tự dựng cây phải theo Euler tour tin, không phải theo độ sâu. Sắp theo depth làm tính chất "LCA cặp liên tiếp là đủ" không còn đúng và cây dựng sai.
Sai biên trong vòng pop: điều kiện phải là dep[st.top()] > dep[l] (lớn hơn thật sự). Dùng >= sẽ pop nhầm chính đỉnh $l$ khi nó đã nằm trong stack, gây nối cạnh sai hoặc vòng lặp hỏng. Luôn giữ lại ít nhất 1 phần tử (st.size() >= 2).
Tràn số khi tính khoảng cách / Steiner. Với $N$ tới $2 \cdot 10^{5}$ và trọng số cạnh lớn, tổng khoảng cách dễ vượt int. Dùng long long cho dist[] và biến cộng dồn.
up[u][0] của gốc trỏ về chính nó (hoặc 0 ảo). Nếu để up[root][0] không khởi tạo, lca có thể nhảy ra ngoài mảng. Đặt up[root][0] = root (gốc tự làm cha) là an toàn.
Trường hợp biên $K = 1$ . Cây ảo chỉ có một đỉnh, không có cạnh; code phải chạy đúng (vòng for thêm LCA không chạy, stack xả về 1 phần tử). Đừng giả định luôn có ít nhất một cạnh.

Biến thể / Mở rộng

DP trên cây ảo: sau khi dựng vadj[], chạy DFS trên cây ảo với trạng thái phân biệt "đỉnh quan trọng" và "đỉnh Steiner (LCA thêm vào)". Đây là khung chuẩn cho các bài DP nhiều truy vấn (vd CF Tree and Queries dạng nâng cao).
LCA $O (1)$ : thay binary lifting bằng Euler tour + Sparse Table trên mảng độ sâu để mỗi LCA còn $O (1)$ , đưa mỗi truy vấn về $O (K \log K)$ thuần do sort.
Cạnh có trọng số: lưu thêm dis[u] = khoảng cách từ gốc tới $u$ ; trọng số cạnh ảo $(p, c) = d i s [c] - d i s [p]$ .
Liên hệ: kỹ thuật này dựa trực tiếp trên LCA và Euler tour, xem thêm Cây Fenwick / Segment Tree cho các bài kết hợp truy vấn trên đường đi.

Bài tập luyện

Lưu ý: pool CTOJ hiện chưa có bài thuần virtual tree. Các bài dưới đây rèn nền tảng bắt buộc của kỹ thuật này (LCA, khoảng cách qua LCA, gộp thông tin trên đường đi) — nắm vững chúng trước khi làm bài cây ảo thật.

Truy vấn khoảng cách (distqry) — (Advanced) tính khoảng cách giữa hai đỉnh bằng $depth [a] + depth [b] - 2 depth [l c a (a, b)]$ — đúng công thức trọng số cạnh ảo.
Tổ tiên chung thấp nhất (compqry2) — (Advanced) cài LCA bằng binary lifting trong $O (\log N)$ , viên gạch lõi để dựng virtual tree.
Cú Bay Đêm (running) — (Veteran) kết hợp LCA với difference-on-tree để cộng dồn theo đường đi $s \to t$ ; luyện tư duy "đường đi tách tại LCA" mà cây ảo khai thác.