---
title Virtual/Auxiliary Tree (Cây ảo)
---

# Virtual/Auxiliary Tree (Cây ảo)

[TOC]

## Giới thiệu

Mục đích của bài viết là để giới thiệu về một kỹ thuật trên cây xuất hiện khá gần đây: **cây ảo (virtual tree)**. Về cơ bản, cây ảo chính là một cách khác để **biểu diễn** cây hiện tại thành một dạng "nén" và sử dụng linh hoạt trong một số bài toán.

## Lưu ý trước khi đọc

Trước khi bắt đầu bài viết, tụi mình cần các bạn có một số kiến thức về:
- [Cây đồ thị](https://usaco.guide/silver/intro-tree)
- [Tổ tiên chung gần nhất](https://cp-algorithms.com/graph/lca_binary_lifting.html)
- [Euler tour](https://vnoi.info/wiki/algo/graph-theory/euler-tour-on-tree.md)

Giờ thì chúc mọi người đọc bài viết vui vẻ.

## Bài toán mở đầu
Cho một cây gồm $N$ đỉnh không trọng số với $Q$ truy vấn. Mỗi truy vấn có dạng :
- $k \ a_1 \ a_2 \ a_3 \ ... \ a_k$ ($\text{với }a_i \neq a_j \ \text{khi} \ i \neq j$ ). Tính tổng $d(a_i, a_j)$ với mọi $1 \leq i < j \leq k$, trong đó $d(u, v)$ là **số cạnh** trên đường đi đơn từ đỉnh $u$ đến đỉnh $v$ trên cây.

Giới hạn : $1 \leq N, Q \leq 3 \times 10^5$, tổng $k$ trong $Q$ truy vấn không vượt quá $3 \times 10^5$.

## Hướng tiếp cận: Trâu tất cả các cặp
Trong thuật toán trâu, trong mỗi truy vấn ta chỉ cần duyệt qua $C^2_k$ cặp đỉnh và tính tổng $d(a_i, a_j)$. Nếu ta sử dụng Nhảy nhị phân (Binary jumping) thì ta sẽ tính được một cặp trong độ phức tạp $O(\log_2(n))$, còn sử dụng Đường đi Euler trên cây sẽ cho ta độ phức tạp "ổn hơn" là $O(1)$. Tuy nhiên thì cả 2 phương pháp tính từng cặp này sẽ không hiệu quả.

Độ phức tạp tệ nhất cho mỗi truy vấn sẽ là $O(k^2)$

## Hướng tiếp cận: Trâu O(N)

Ta có một nhận xét quan trọng sau :
- Với mỗi cạnh $(u, v)$, ta đếm số cặp đỉnh $(x, y)$ sao cho $x$ và $y$ thuộc truy vấn và để đi từ đỉnh $x$ đến đỉnh $y$, ta phải đi qua cạnh $(u, v)$. Đáp án sẽ là tổng của các giá trị này cho tất cả các cạnh.
- Xét cạnh $(u, v)$, khi loại bỏ cạnh này, cây sẽ tách ra thành $2$ thành phần liên thông. Gọi $X$, $Y$ là số đỉnh thuộc truy vấn ở mỗi thành phần liên thông, sẽ có $X \times Y$ cặp đỉnh $(x, y)$ thỏa điều kiện nêu trên.


Vậy bài toán của ta sẽ trở thành : đếm số lượng các cặp đỉnh $(a_i, a_j)$ đi qua cạnh $(u, v)$ nào đó, đáp án của ta chính là tổng số cặp đỉnh thỏa điều kiện như vậy.

Độ phức tạp của ta bây giờ với mỗi truy vấn là $O(N)$, nên tổng độ phức tạp tệ nhất là $O(Q \times N)$

:::spoiler **Code mẫu**

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5+5;

int n, k, a[N], sz[N];
vector<int> g[N];
long long ans = 0;

void dfs_solve(int u, int e){
    //duyệt qua cả cây
    for(int v : g[u]) if(v != e){
        dfs_solve(v, u);
        sz[u] += sz[v];
        //số lượng đỉnh thuộc truy vấn trong cây con gốc u
    }

    if(e != -1){
        //tính số cặp (a[i], a[j]) đi qua cạnh (u, cha của u)
        ans += 1ll * sz[u] * (k-sz[u]);
    }
}

void solve_query(){
    cin >> k;
    for(int i = 1; i <= k; ++i){
        cin >> a[i]; 
        sz[a[i]] = 1;
        //khởi tạo tại đỉnh a[i] là một đỉnh trong truy vấn
    }

    ans = 0; dfs_solve(1, -1); //tính truy vấn
    cout << ans << '\n';
    for(int i = 1; i <= n; ++i) sz[i] = 0; //reset mảng sz
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int q; cin >> q;
    while(q--) solve_query();

    return 0;
}

:::

## Hướng tiếp cận: Dựng Cây Ảo

Với hướng tiếp cận $O(N)$ với mỗi truy vấn, ta nhận thấy được nhiều **khuyết điểm** của thuật $O(N)$ là do ta sử dụng quá nhiều **cạnh** và **đỉnh** không cần thiết. Vì vậy ta cần phải có những nhận xét để tối ưu, sử dụng ít đỉnh và ít cạnh nhất có thể.

### Sử dụng cạnh có trọng số
Giả sử hai đỉnh $u$ và $v$ đều $\in k$ đỉnh trong truy vấn và trên đường đi từ $u$ đến $v$ không tồn tại đỉnh nào khác thuộc những đỉnh trong truy vấn.


Có thể thấy rằng tất cả các cạnh nằm trên đường đi từ $u$ đến $v$ đều có cùng giá trị $X$ và $Y$ (theo định nghĩa ở trên). Ta đã duyệt $T = d(u, v)$ cạnh có vai trò như nhau một cách rất lãng phí. Thay vào đó, ta chỉ cần tính $1$ lần rồi nhân giá trị tính được cho $T$.

Từ đó, ta có ý tưởng: Thay vì duyệt lại $T$ cạnh có vai trò như nhau, ta sẽ tạo ra một cạnh "nén" có vai trò giống với những cạnh này trong một cây mới gọi là **cây ảo**, rồi gán trọng số cho cạnh "nén" là $d(u, v)$ ($u$ và $v$ là hai đỉnh thuộc truy vấn).


### Xây dựng tập đỉnh cho cây ảo

Bây giờ, mục tiêu của chúng ta là dựng một cây mới (gọi là **cây ảo**) sao cho cây này chứa:

- Tất cả các đỉnh thuộc truy vấn.
- Các cạnh trên đường đi giữa mọi cặp đỉnh thuộc truy vấn, những cạnh này có thể tồn tại dưới dạng cạnh "nén" (theo ý tưởng tối ưu được nêu trên).

Tuy nhiên, nếu chỉ sử dụng những đỉnh thuộc truy vấn thì vẫn chưa đủ. Khi nén cạnh ta cần phải có những đỉnh làm "trung gian" cho nhiều cạnh đi qua.

Ví dụ trong hình sau :


Ta không thể cứ để $3$ đỉnh $a, b, c$ như vậy trong **cây ảo** của ta, ta phải có đỉnh $m$ kết nối với $a, b,$ và $c$.

Thế là một vấn đề mới lại được đặt ra là **số đỉnh** trong **cây ảo** (gọi là đỉnh "quan trọng") ta cần dựng ít nhất là bao nhiêu?

:::success
**Câu trả lời** là nhỏ hơn $2k$.
:::

Đầu tiên, tập hợp những đỉnh "quan trọng" đó chắc chắn sẽ bao gồm $k$ đỉnh trong truy vấn và chúng phải là **tổ tiên chung gần nhất** của **ít nhất 1 cặp đỉnh trong truy vấn**.

Ta sẽ **sắp xếp** lại $a$ theo **thứ tự duyệt DFS** và thêm vào tập hợp những **tổ tiên chung gần nhất** (LCA) của $k-1$ cặp đỉnh $(a_i, a_{i+1})$ (với mọi $1 \leq i < k$), rồi loại bỏ các đỉnh bị trùng. Tập hợp những đỉnh đó của ta bây giờ sẽ chính là những đỉnh cần thiết cho cây mới.

Bây giờ, ta chỉ cần chứng minh, với mọi cặp đỉnh bất kì thuộc truy vấn, LCA của chúng tồn tại trong danh sách được xây dựng như trên. Khi đó, tất cả những cạnh cần được xét sẽ nằm trong cây ảo dưới dạng cạnh "nén".

### Chứng minh: Trong danh sách luôn tồn tại LCA của mọi cặp đỉnh

- Sắp xếp lại cái đỉnh theo thứ tự DFS.
- Ta có những quy ước sau:
- $u, v$ là hai đỉnh trong danh sách
- $T_a$ là cây con gốc $a$
- $u$ có thứ tự DFS nhỏ hơn $v$
- $w=LCA(u, v)$
- $T_c$ được gọi **cây con trực tiếp** của $T_p$ khi và chỉ khi tồn tại cạnh $(p, c)$ và $c \in T_p$
- Ta có một vài trường hợp sau :
- $u$ hoặc $v$ là tổ tiên của đỉnh còn lại (luôn đúng trong thuật toán)
- $u$ và $v$ kề nhau trong danh sách (luôn đúng trong thuật toán)
- Xét $T_w$:
- Có $>2$ **cây con trực tiếp** chứa ít nhất $1$ đỉnh thuộc danh sách thì bản chất sẽ luôn tồn tại $w$ trong tập hợp những đỉnh quan trọng. (Vì chỉ cần lấy $LCA$ của **đỉnh cuối** trong một cây con và **đỉnh đầu tiền** xuất hiện trong cây con liền kề mà nó thăm thì ta đã có được $w$) 
- Trong hình vẽ, các đỉnh có tên là những đỉnh có trong danh sách. Ví dụ ta thăm lần lượt cây con 1, 2, 3 trong hình. Ta thấy $x$ sẽ kề $y$ trong danh sách nên sẽ tồn tại $w$ trong tập hợp của chúng ta.
- Điều này cũng sẽ luôn đúng vì **đỉnh cuối** của cây con hiện tại chắc chắn sẽ kề với **đỉnh đầu** của cây con kề nó.
- Có đúng $2$ **cây con trực tiếp** thỏa điều kiện thì hiển nhiên, đỉnh cuối cùng trong cây con chứa $u$ và đỉnh đầu tiên trong cây con chứa $v$ sẽ là $w$. Vậy tính đúng đắn của thuật toán đã được chứng minh.

### Dựng các cạnh cho cây ảo

Bây giờ ta sẽ đến với việc xây dựng cạnh cho cây ảo.

Sau khi dựng hết tập hợp những đỉnh cần thiết, ta lại tiếp tục sắp xếp chúng theo thứ tự duyệt DFS.

Ta sẽ từ thứ tự DFS và Đường đi Euler trên cây để "tìm" lại các cạnh.

Giả sử ta đang có tập hợp đỉnh sau khi sắp xếp lại là $r_1, r_2, r_3, ...r_q$. Ta cần chọn ra một **gốc** để đặt làm đỉnh của cây khi dựng cạnh, để xử lý bước này dễ nhất có thể, ta sẽ chọn **đỉnh có thức tự DFS sớm nhất**, chính là $r_1$.

Tiếp theo, ta cần phải tìm **cha** cho các đỉnh còn lại. Để tìm cha của một đỉnh, ta cần phải quan tâm **nhánh cây**.

Khi chuyển từ nhánh $r_1 \ \rightarrow \cdots \rightarrow r_x \rightarrow \cdots \rightarrow r_j$ sang nhánh $r_1 \rightarrow \cdots \rightarrow r_x \rightarrow \cdots \rightarrow r_i$, ta cần phải có một **cấu trúc dữ liệu** để lưu lại một phần của nhánh trước đó. Đó chính là `stack`.

Ý tưởng là `stack` ban đầu của ta chứa $r_1$, ta sẽ xét từ $i = 2, 3, \cdots, q$, nếu **cây con gốc** đầu `stack` hiện tại vẫn không chứa đỉnh $r_i$ (tức là đã sinh ra nhánh cây mới), thì ta sẽ bỏ đi đỉnh `stack` cho đến khi nào cây con gốc đầu `stack` của ta chứa $r_i$. Sau đó, ta sẽ thêm cạnh $r_i$ hiện tại với đầu `stack` (hay chính là cha của $r_i$).

Ví dụ, cho cây sau và danh sách $r = [r_1, \cdots, r_x, r_y, r_j, r_i, \cdots]$, ta sẽ chuyển từ $r_j$ sang $r_i$ như sau:


Theo thuật toán được nêu trên, khi xét nhánh $r_1 \rightarrow \cdots \rightarrow r_x \rightarrow r_y \rightarrow r_j$, để chuyển sang nhánh chứa $r_i$, ta sẽ bỏ đi $r_y$ và $r_j$. Như vậy, $r_x$ sẽ là cha trực tiếp của $r_i$ trong cây ảo và cạnh kết nối hai nút này có trọng số là $3$.

Sau khi xây dựng cạnh $(r_x, r_i)$, ta lại thêm $r_i$ vào đỉnh `stack` và tiếp tục duyệt danh sách $r$.

Cuối cùng, ta lại áp dụng thuật toán $O(n)$ ở phần trước cho cây ảo vừa dựng được. Tuy nhiên, lúc này cây ảo của chúng ta chỉ có tối đa $2k - 1$ nút nên độ phức tạp trở thành $O(k)$.

:::spoiler **Code mẫu**

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+5;

int n, q, depth[N], tin[N], tout[N], dfs_timer, par[N][20];
vector<int> g[N];

void dfs(int u, int e){
    tin[u] = ++dfs_timer; //thứ tự DFS
    for(int v : g[u]) if(v != e){
        depth[v] = depth[u] + 1; par[v][0] = u;
        for(int i = 1; i <= 17; ++i){
            par[v][i] = par[par[v][i-1]][i-1];
        } //chuẩn bị cho bước tìm LCA bằng binary jumping
        dfs(v, u);
    }
    tout[u] = dfs_timer;
}

//comparator thứ tự DFS
bool dfsTimer(int u, int v){
    return tin[u] < tin[v];
}

//kiểm tra cây con gốc u có chứa v
bool inside(int u, int v){
    return tin[u] <= tin[v] and tout[v] <= tout[u];
}

//tìm LCA
int getLCA(int u, int v){
    if(inside(u, v)) return u;
    if(inside(v, u)) return v;
    for(int i = 17; i >= 0; --i){
        if(depth[u] >= (1<<i) and !inside(par[u][i], v)){
            u = par[u][i];
        }
    }
    return par[u][0];
}

//đây là những mảng, biến sử dụng trong Virtual Tree
//sum[u] là số đỉnh thuộc cây con gốc u và nằm trong k đỉnh truy vấn
//minigraph[u] là danh sách kề của đỉnh u
//st là stack để tìm cạnh
//ans là đáp án cho truy vấn hiện tại
//VT_size là số đỉnh trong Virtual Tree
int k, a[N], sum[N], VT_size;
long long ans;
vector<int> minigraph[N];
stack<int> st;

void solve(int u, int e){
    for(int v : minigraph[u]) {
        solve(v, u);
        //tính tổng số đỉnh thuộc truy vấn trong cây con gốc u
        sum[u] += sum[v];
    }

    if(e != -1){
        //tính số cặp x y như mô tả trước đó
        ans += 1ll * (depth[u] - depth[e]) * sum[u] * (VT_size - sum[u]);
    }
}

void solve_query(){
    cin >> k;
    for(int i = 1; i <= k; ++i){
        cin >> a[i]; sum[a[i]] = 1; //khởi tạo sum[a[i]]=1
    }
    //sắp xếp theo thứ tự DFS
    sort(a + 1, a + 1 + k, dfsTimer);
    
    //thêm vào tập hợp LCA của 2 cặp đỉnh liên kề
    for(int i = 1; i < k; ++i){
        a[i+k] = getLCA(a[i], a[i+1]);
    }

    k = 2 * k - 1; //số đỉnh hiện tại sau khi thêm
    sort(a + 1, a + 1 + k, dfsTimer); 
    k = unique(a + 1, a + 1 + k) - a - 1; //sắp xếp và rời rạc hóa

    while(!st.empty()) st.pop(); //clear stack
    st.push(a[1]); //khởi tạo stack
          
    for(int i = 2; i <= k; ++i){
        //kiểm tra nhánh cây
        while(!inside(st.top(), a[i])){
            st.pop();
        }
        //thêm cạnh 
        minigraph[st.top()].push_back(a[i]);
        st.push(a[i]);
    }


    //tính đáp án
    VT_size = k; ans = 0; solve(a[1], -1);
    cout << ans << '\n';

    //khởi tạo lại danh sách kề và mảng sum
    for(int i = 1; i <= k; ++i){
        minigraph[a[i]].clear(); sum[a[i]] = 0;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for(int i=1; i<n; ++i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 1);
    while(q--){
        solve_query();
    }

    return 0;
}

:::

## Thuật toán Virtual Tree (Cây ảo)
Tổng quát lại thuật toán dựng Cây ảo :
- Sắp xếp $a_1, a_2, a_3, ..., a_k$ theo thứ tự DFS.
- Thêm vào tập hợp những đỉnh quan trọng trong cây ảo ta dựng $a_1, a_2, a_3, ..., a_k, LCA(a_1, a_2), LCA(a_2, a_3), ..., LCA(a_{k-1}, a_k)$.
- Sắp xếp lại danh sách đỉnh "quan trọng" theo thứ tự DFS.
- Rời rạc hóa danh sách
- Dựng lại các cạnh với trọng số bằng `stack`. Khi cây con có gốc là đỉnh đầu `stack` không chứa đỉnh đang xét hiện tại, thì ta sẽ `pop` cho đến khi gặp nhánh mới.
- Xây dựng cạnh trong cây ảo từ đỉnh đầu `stack` (cha) đến đỉnh đang xét (con) với trọng số là khoảng cách của $2$ nút này trên cây thật.
- Độ phức tạp cho mỗi việc dựng cây ảo: $O(k \log n)$.

Sau đây là animation minh họa cho quá trình xây dựng virtual tree:

<iframe width="672" height="378" src="https://www.youtube.com/embed/QGKKtDwlx8w?si=xrUTo1SNFLcWg74n" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>

## Bài tập áp dụng

[Codeforces Round 339 (Div. 1) D](https://codeforces.com/contest/613/problem/D)

[Bedao OI Contest 1 - Bài 1 : Đếm cầu](https://oj.vnoi.info/problem/bedao_oi1_a)

# Tài liệu tham khảo
[CP Tutorial: Virtual/Auxiliary Tree by Radoslav Dimitrov](https://www.youtube.com/watch?v=czySm7bUHgY&t=2320s)