Virtual Tree

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

huunguyen · Last updated 8, Tháng 4, 2026, 16:09

Virtual Tree (cây ảo) là kỹ thuật nén cây gốc thành cây con chỉ chứa tập đỉnh quan trọng và LCA của chúng, giảm kích thước từ $O (N)$ xuống $O (K)$ với $K$ là số đỉnh quan trọng.

Ứng dụng: Bài toán trên cây với nhiều truy vấn, mỗi truy vấn chỉ quan tâm đến $K ≪ N$ đỉnh.

Ý tưởng

Cho tập $K$ đỉnh quan trọng ${v_{1}, v_{2}, \dots, v_{K}}$ . Virtual tree của tập này gồm:

Tất cả $K$ đỉnh quan trọng.
LCA của mọi cặp đỉnh liên tiếp (theo thứ tự DFS/Euler tour).
LCA của đỉnh đầu và đỉnh cuối (để đảm bảo gốc được bao phủ).

Tổng số đỉnh trong virtual tree $\leq 2 K - 1$ .

Tiền xử lý

Cần:

Euler tour (tin[u]): thứ tự vào của DFS.
LCA trong $O (1)$ hoặc $O (\log N)$ (dùng Sparse Table hoặc binary lifting).
depth[u]: độ sâu mỗi đỉnh.

Xây dựng Virtual Tree

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

vector<int> adj[MAXN];
int tin[MAXN], depth[MAXN], par[MAXN][LOG];
int timer_val = 0;

void dfs(int u, int p, int d) {
    tin[u] = timer_val++;
    depth[u] = d;
    par[u][0] = p;
    for (int j = 1; j < LOG; j++)
        par[u][j] = par[par[u][j-1]][j-1];
    for (int v : adj[u])
        if (v != p) dfs(v, u, d+1);
}

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

// Xây virtual tree từ tập đỉnh key[]
// Trả về danh sách cạnh của virtual tree
vector<pair<int,int>> build_virtual_tree(vector<int> key) {
    // Sắp xếp theo thứ tự Euler tour
    sort(key.begin(), key.end(), [](int a, int b){ return tin[a] < tin[b]; });
    key.erase(unique(key.begin(), key.end()), key.end());

    // Thêm LCA của các cặp liên tiếp
    int sz = key.size();
    for (int i = 0; i + 1 < sz; i++)
        key.push_back(lca(key[i], key[i+1]));
    // Thêm LCA tổng quát (gốc ảo nếu cần)
    // key.push_back(lca(key[0], key[sz-1]));

    sort(key.begin(), key.end(), [](int a, int b){ return tin[a] < tin[b]; });
    key.erase(unique(key.begin(), key.end()), key.end());

    // Xây cây bằng stack
    vector<pair<int,int>> edges;
    stack<int> st;
    for (int u : key) {
        if (st.empty()) { st.push(u); continue; }
        int l = lca(u, st.top());
        if (l != st.top()) {
            while (st.size() > 1 && depth[st.top()] > depth[l]) {
                int child = st.top(); st.pop();
                int parent = (depth[st.top()] <= depth[l]) ? l : st.top();
                edges.push_back({parent, child});
            }
            if (st.top() != l) { st.push(l); }
        }
        st.push(u);
    }
    while (st.size() > 1) {
        int child = st.top(); st.pop();
        edges.push_back({st.top(), child});
    }
    return edges;
}

Ví dụ sử dụng

Bài toán: Cho $Q$ truy vấn, mỗi truy vấn cho $K$ đỉnh, tính tổng trọng số cạnh của Steiner tree (cây nhỏ nhất nối $K$ đỉnh):

// Tổng trọng số Steiner tree = (tổng dist[lca(v_i, v_{i+1})] cho cặp liên tiếp) / 2
// Với dist[u] = khoảng cách từ gốc đến u

long long steiner_tree(vector<int>& key, vector<long long>& dist) {
    sort(key.begin(), key.end(), [](int a, int b){ return tin[a] < tin[b]; });
    long long ans = 0;
    int sz = key.size();
    for (int i = 0; i + 1 < sz; i++)
        ans += dist[key[i]] + dist[key[i+1]] - 2 * dist[lca(key[i], key[i+1])];
    ans += dist[key[0]] + dist[key[sz-1]] - 2 * dist[lca(key[0], key[sz-1])];
    return ans / 2;
}

Độ phức tạp

Xây virtual tree: $O (K \log K)$ (sort + LCA).
Xử lý DP trên virtual tree: $O (K)$ .
Tổng cho $Q$ truy vấn: $O (\sum K_{i} \log K_{i})$ .

Khi nào dùng Virtual Tree?

Bài DP trên cây với $Q$ truy vấn, mỗi truy vấn chỉ quan tâm $K$ đỉnh ( $\sum K \leq 10^{6}$ ).
Bài toán Steiner tree, dominator tree trên tập đỉnh nhỏ.
Tối ưu từ $O (N Q)$ xuống $O (\sum K \log K)$ .

Bình luận

Không có bình luận tại thời điểm này.