# Giới thiệu về Virtual/Auxiliary Tree (Cây ảo)

[TOC]
## 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$ (với $a_i \neq a_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à khoảng cách ngắn nhất 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 sẽ là $O(N^2)$

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

:::

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

- Ta có một nhận xét quan trọng sau :
+ Trong một truy vấn, ta giả sử xét cạnh $(u, v)$, nếu khi **loại bỏ cạnh này** mà **hai thành phần liên thông** sinh ra vẫn tồn tại ít nhất một đỉnh $\in$ $k$ đỉnh trong truy vấn thì ta sẽ cộng đáp án lên **tích** số đỉnh $\in$ thành phần liên thông thứ nhất với số đỉnh $\in$ thành phần liên thông thứ hai.
+ Hãy xem hình sau : 
+ Lúc này, cặp $(u, v)$ mà ta đang xét sẽ có $X \times Y$ cặp đỉnh $(a_i, a_j)$ với lúc này $a_i \in$ thành phần liên thông thứ nhất và $a_j \in$ thành phần liên thông thứ hai.

- 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 với mỗi cạnh $(u, v)$

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

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

:::

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

- Từ hướng tiệp cận $O(N)$ với mỗi truy vấn, ta cần có một số tối ưu để thuật toán nhanh hơn. Giả sử hai đỉnh $u$ và $v$ đều $\in k$ đỉnh trong truy vấn và giả thuyết giữa $u$ và $v$ không tồn tại đỉnh nào khác thuộc những đỉnh trong truy vấn. 

- Ta thấy rằng giữa $u$ và $v$ vốn không có đỉnh nào khác "đặc biệt", nhưng ta lại phải duyệt cả $T$ cạnh ($T$ là $d(u, v)$). Vậy nên ta cần có một "thứ gì đó" để dựng lại một đồ thị khác gồm không quá nhiều đỉnh (vì nếu không thuật toán sẽ trở lại $O(N)$ cho mỗi truy vấn) và số cạnh cần xét là tối ưu nhất có thể.

### Trọng số cạnh
- Thay vì "duyệt lại" $d(u, v)$, ta sẽ **gán** trọng số trong đồ thị mới với cạnh $(u, v)$ là $d(u, v)$. Ta đã giải quyết được **vấn đề** duyệt cạnh.


### Đỉnh "quan trọng"

- Tuy nhiên một vấn đề mới lại được đặt ra là **số đỉnh** trong **cây mới** ta cần dựng ít nhất là bao nhiêu?

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

- Tập hợp những đỉnh "quan trọng" đó chắc chắn sẽ bao gồm $k$ đỉnh trong truy vấn

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

:::spoiler **Chứng minh**
- Giả sử xét hai đỉnh $u$ và $v$ trong truy vấn hiện tại. Sẽ có hai trường hợp sau :
+ $u$ hoặc $v$ là tổ tiên của đỉnh còn lại : trường hợp này ta không cần xét vì trong tập hợp gốc của ta vốn chứa đỉnh là tổ tiên của đỉnh còn lại.
+ $u$ và $v$ nằm trong hai cây con $T_u$ và $T_v$ phân biệt. Không mất tính tổng quát, giả sử ta duyệt $u$ trước $v$ theo thứ tự DFS. Nếu $u$ kề $v$ sau khi sắp xếp theo **thứ tự từ điển**, $LCA(u, v)$ sẽ xuất hiện trong tập hợp của ta. Ngược lại, điều này đồng nghĩa với việc khi ta xét đoạn $p_l=u, p_{l+1}, p_{l+2}, ..., p_r=v$, ta có $p_{l+1}, p_{l+2}, ... p_{r-1} \in T_u$, nên $LCA(p_l=u, v) = LCA(p_{l+1}, v) = LCA(p_{l+2}, v) = ... = LCA(p_{r-1}, v)$
:::
### Dựng cạnh
- Bây giờ ta sẽ đến với việc xây dựng cạnh cho Cây Ảo của chúng ta.
- 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**, các bạn hãy xem hình sau
- Khi chuyển từ nhánh $r_1 \ - \ ... \ - \ u \ - \ v$ sang nhánh $r_1 \ - \ ... \ - \ u \ - \ w$, 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, ..., q$, nếu đầ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ẽ `pop` cho đến khi nào cây con đầ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 $p_i$).

- Các bạn có thể xem ví dụ sau để dễ hình sau:


- Ta gọi `stack` của ta là $s$. hiện tại, nhánh của ta đang là $s=${$r_1, ..., u, ..., v$}. Lúc này $u$ là tổ tiên chung gần nhất giữa $v$ và $w$. Khi tới đỉnh $w$ ta sẽ lần lượt `pop` các đỉnh sau đỉnh $u$, sau đó `stack` của ta sẽ trở thành $s=${$r_1, ..., u$}, sau đó ta sẽ thêm cạnh $(u, w)$ và `push` $w$ vào $s$.

- Vậy ta đã kết thúc việc xây dựng ý tưởng của thuật toán mở đầu.

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

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+5;

int n, q, dfs_timer, VirtualTreeSize, h[N], tin[N], tout[N], par[N][20], sz[N];
vector<int> g[N], minigraph[N];

/* NOTE
sz[u] : tổng số đỉnh thuộc truy vấn trong cây con gốc u của Cây ảo

g là danh sách kề của cây gốc
minigraph là danh sách kề của Cây ảo 
*/

void dfs(int u, int e){
    tin[u]=++dfs_timer;
    for(int v:g[u]) if(v!=e){
        h[v]=h[u]+1; par[v][0]=u;

        for(int i=1; i<=17; ++i){
            par[v][i]=par[par[v][i-1]][i-1];
        }

        dfs(v, u);
    }
    tout[u]=dfs_timer;
}

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

//Tìm tổ tiên chung gần nhất giữa u và v
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(h[u]>=(1<<i) and !inside(par[u][i], v)){
            u=par[u][i];
        }
    }

    return par[u][0];
}

//Hàm so sánh thứ tự duyệt DFS
bool dfsTimer(int u, int v){
    return tin[u]<tin[v];
}

//Duyệt xử lý trên Cây ảo được nén từ Cây gốc
long long dfs_minigraph(int u, int e){
    long long res=0;

    for(int v:minigraph[u]) if(v!=e){
        //Tổng đáp án của mỗi cạnh trước đó
        res+=dfs_minigraph(v, u);
        
        //tính tổng số đỉnh thuộc truy vấn trong cây con gốc u
        sz[u]+=sz[v]; 
    }

    if(e!=-1){
        // Dễ thấy do e là cha của u trên Cây ảo
        // nên d(e, u) cũng chính là h[u]-h[e]
        // sz[u] là số đỉnh thuộc truy vấn trong cây con gốc u
        // VirtualTreeSize - sz[u] là số đỉnh thuộc truy vấn
        // nằm ngoài cây con gốc 
        res+=1ll*(h[u]-h[e])*sz[u]*(VirtualTreeSize-sz[u]);
    }
    return res;
}

void solve_query(){
    //Input truy vấn
    int k; cin>>k;
    vector<int> nodes(k);
    for(int i=0; i<k; ++i) {
        cin>>nodes[i];
        //Do trong Cây ảo, ta sử dụng a[i] hay lúc này là nodes[i]
        //Nên cần phải đánh dấu lại
        sz[nodes[i]]=1;
    }

    //Sắp xếp theo thứ tự DFS
    sort(nodes.begin(), nodes.end(), dfsTimer);
    
    //Thêm vào tập hợp LCA của nodes[i] và nodes[i+1]
    for(int i=0; i+1<k; ++i){
        nodes.push_back(getLCA(nodes[i], nodes[i+1]));
    }

    //Lọc các giá trị phân biệt
    sort(nodes.begin(), nodes.end(), dfsTimer); nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());

    //Khởi tạo stack bằng gốc của Cây ảo
    vector<int> s={nodes[0]}; 

    for(int i=1; i<nodes.size(); ++i){
        //Khi cây con đầu stack không chứa nodes[i] thì pop
        while(!inside(s.back(), nodes[i])){
            s.pop_back();
        }
        //Thêm cạnh đầu stack hiện tại với nodes[i]
        int p=s.back();
        minigraph[p].push_back(nodes[i]);
        minigraph[nodes[i]].push_back(p);

        s.push_back(nodes[i]);
    }

    //Xử lý bài toán mở đầu
    VirtualTreeSize=nodes.size();
    cout<<dfs_minigraph(s[0], -1)<<'\n';

    //Reset lại đồ thị Cây ảo
    for(int i=0; i<VirtualTreeSize; ++i){
        minigraph[nodes[i]].clear(); sz[nodes[i]]=0;
    }
}

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

    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)
- 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)$.
- Dựng lại các cạnh với trọng số bằng `stack`. Khi cây con đầu `stack` của ta không chứa đỉnh đang xét hiện tại thì ta sẽ `pop` cho đến khi gặp.

- Độ phức tạp : $O(3 \times 10^5 \times \log n)$ với mỗi truy vấn sử dụng độ phức tạp $O(k \times \log n)$

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

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+5;

int n, q, dfs_timer, VirtualTreeSize, h[N], tin[N], tout[N], par[N][20], sz[N];
vector<int> g[N], minigraph[N];

void dfs(int u, int e){
    tin[u]=++dfs_timer;
    for(int v:g[u]) if(v!=e){
        h[v]=h[u]+1; par[v][0]=u;

        for(int i=1; i<=17; ++i){
            par[v][i]=par[par[v][i-1]][i-1];
        }

        dfs(v, u);
    }
    tout[u]=dfs_timer;
}

bool inside(int u, int v){
    return tin[u]<=tin[v] and tout[v]<=tout[u];
}

int getLCA(int u, int v){
    if(inside(u, v)) return u;
    if(inside(v, u)) return u;

    for(int i=17; i>=0; --i){
        if(h[u]>=(1<<i) and !inside(par[u][i], v)){
            u=par[u][i];
        }
    }

    return par[u][0];
}

int getDist(int u, int v){
    return h[u]+h[v]-2*h[getLCA(u, v)];
}

bool dfsTimer(int u, int v){
    return tin[u]<tin[v];
}

void solve_query(){
    int k; cin>>k;
    vector<int> nodes(k);
    for(int i=0; i<k; ++i) {
        cin>>nodes[i];
        sz[nodes[i]]=1;
    }

    sort(nodes.begin(), nodes.end(), dfsTimer);
    for(int i=0; i+1<k; ++i){
        nodes.push_back(getLCA(nodes[i], nodes[i+1]));
    }

    sort(nodes.begin(), nodes.end(), dfsTimer); nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());

    vector<int> s={nodes[0]}; 

    for(int i=1; i<nodes.size(); ++i){
        while(!inside(s.back(), nodes[i])){
            s.pop_back();
        }
        int p=s.back();
        minigraph[p].push_back(nodes[i]);
        minigraph[nodes[i]].push_back(p);

        s.push_back(nodes[i]);
    }

    //Xử lý bài toán sau khi dựng xong Cây ảo
}

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

    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;
}

:::

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

[Codeforces Round 339 (Div. 1) D](https://codeforces.com/contest/613/problem/D)
- Tóm tắt đề bài : Cho cây $n$ đỉnh không trọng số và $q$ truy vấn dạng $k \ a_1 \ a_2 \ ... \ a_k$. Với mỗi truy vấn, cần đếm số lượng đỉnh **ít nhất và khác** các đỉnh trong truy vấn cần được bỏ đi để $k$ đỉnh trong truy vấn **đôi một không liên thông** với nhau.

[Bedao OI Contest 1 - Bài 1 : Đếm cầu](https://oj.vnoi.info/problem/bedao_oi1_a)
- Tóm tắt đề bài : Cho **đa đồ thị** $n$ đỉnh $m$ cạnh và $q$ truy vấn. Mỗi truy vấn dạng $a \ b \ c \ d$, cần đếm số lượng **cầu** từ bất kì đường đi đơn từ $c$ đến $d$ sau khi đã thêm cạnh $(a, b)$ vào đồ thị gốc. (Lưu ý, sau mỗi truy vấn, đồ thị gốc không thay đổi)