CÂY ẢO (PHẦN 1/1)

Mục lục

Phần Mở Đầu

Bài viết này nhằm giới thiệu một kỹ thuật xử lý cây tương đối mới: cây ảo (virtual tree). Về bản chất, cây ảo là một phương pháp khác để biểu diễn cây gốc dưới một dạng “nén”, giúp giải quyết một số bài toán một cách linh hoạt và hiệu quả hơn.

Những Điều Cần Biết Trước

Trước khi đi sâu vào nội dung về cây ảo, các bạn đọc cần có kiến thức nền tảng về:

Chúc các bạn có một trải nghiệm đọc bài thú vị.

Bài Toán Khởi Động

Cho một cây không trọng số gồm $$N$$ đỉnh và $$Q$$ truy vấn. Mỗi truy vấn được định nghĩa như sau:

$k \ a_1 \ a_2 \ a_3 \ … \ a_k$ (trong đó $\text{với }a_i \neq a_j \ \text{khi} \ i \neq j$$ ). Yêu cầu tính tổng khoảng cách $d(a_i, a_j)$ cho tất cả các cặp $(i, j)$ thỏa mãn $1 \leq i < j \leq k$. Ở đây, $d(u, v)$ là số lượng cạnh trên đường đi đơn duy nhất giữa hai đỉnh $u$ và $v$ trong cây.

Giới hạn của bài toán: $1 \leq N, Q \leq 3 \times 10^5$, và tổng số lượng $k$ qua tất cả các truy vấn không vượt quá $3 \times 10^5$.

Phương Pháp Tiếp Cận: Duyệt Mọi Cặp (Brute-force)

Với phương pháp “trâu bò” cơ bản, mỗi truy vấn yêu cầu ta duyệt qua tất cả $C^2_k$ cặp đỉnh để tính tổng $d(a_i, a_j)$. Để tính $d(a_i, a_j)$, ta có thể dùng thuật toán Nhảy Nhị Phân (Binary Jumping) với độ phức tạp $O(\log_2(n))$ cho mỗi cặp, hoặc sử dụng Duyệt Euler trên cây để đạt độ phức tạp $O(1)$ cho mỗi cặp. Dù vậy, việc tính toán cho từng cặp như thế này đều không đủ hiệu quả.

Độ phức tạp trong trường hợp xấu nhất cho mỗi truy vấn sẽ là $O(k^2)$.

Phương Pháp Tiếp Cận: Duyệt O(N) (Brute-force Cải Tiến)

Chúng ta có một nhận định quan trọng như sau:

Đối với mỗi cạnh $(u, v)$ trong cây, ta hãy đếm số lượng cặp đỉnh $(x, y)$ (từ tập các đỉnh của truy vấn) sao cho đường đi duy nhất từ $x$ đến $y$ bắt buộc phải đi qua cạnh $(u, v)$. Kết quả cuối cùng của truy vấn chính là tổng của các số đếm này trên tất cả các cạnh của cây.
Khi xem xét một cạnh $(u, v)$, nếu ta tạm thời loại bỏ cạnh này, cây sẽ bị chia thành $2$ thành phần liên thông riêng biệt. Gọi $X$ và $Y$ lần lượt là số lượng đỉnh thuộc tập truy vấn nằm trong mỗi thành phần liên thông đó. Khi đó, sẽ có chính xác $X \times Y$ cặp đỉnh $(x, y)$ (mà $x$ và $y$ thuộc tập truy vấn) thỏa mãn điều kiện là đường đi giữa chúng phải qua cạnh $(u, v)$.

Như vậy, bài toán được chuyển thành: với mỗi cạnh $(u, v)$, đếm số cặp $(a_i, a_j)$ mà đường đi giữa chúng đi qua $(u, v)$. Đáp án là tổng số lượng các cặp như vậy.

Lúc này, độ phức tạp cho mỗi truy vấn là $O(N)$, dẫn đến độ phức tạp tổng thể trong trường hợp xấu nhất là $O(Q \times N)$.

Mã Nguồn Tham Khảo

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5+5;

int n, k, a[N], sz[N];
vector 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;
}

Phương Pháp Tiếp Cận: Xây Dựng Cây Ảo

Với phương pháp tiếp cận có độ phức tạp $O(N)$ cho mỗi truy vấn, ta có thể thấy rõ những hạn chế của nó: việc duyệt qua quá nhiều cạnh và đỉnh không cần thiết làm cho thuật toán $O(N)$ trở nên chậm. Do đó, chúng ta cần những nhận xét tinh tế hơn để tối ưu hóa, nhằm sử dụng ít đỉnh và cạnh nhất có thể.

Sử Dụng Cạnh Có Trọng Số

Giả sử có hai đỉnh $u$ và $v$ đều thuộc tập $k$ đỉnh của truy vấn, và trên đường đi đơn giữa $u$ và $v$ không có bất kỳ đỉnh nào khác cũng thuộc tập $k$ đỉnh đó.

Dễ thấy rằng tất cả các cạnh trên đường đi từ $u$ đến $v$ đều có cùng đóng góp vào giá trị $X$ và $Y$ (như đã định nghĩa ở phần trước). Việc chúng ta duyệt qua tất cả $T = d(u, v)$ cạnh này, vốn có vai trò tương tự nhau, là một sự lãng phí. Thay vào đó, ta chỉ cần tính toán một lần duy nhất rồi nhân kết quả đó với $T$.

Từ đây, nảy sinh ý tưởng: thay vì duyệt lặp đi lặp lại $T$ cạnh có vai trò giống hệt nhau, chúng ta sẽ tạo ra một cạnh “nén” duy nhất đại diện cho tất cả các cạnh này. Cạnh “nén” này sẽ nằm trong một cây mới, gọi là cây ảo. Trọng số của cạnh “nén” này sẽ được gán bằng $d(u, v)$ (với $u$ và $v$ là hai đỉnh thuộc tập truy vấn).

Xây Dựng Tập Hợp Đỉnh Cho Cây Ảo

Hiện tại, mục tiêu của chúng ta là xây dựng một cây mới (gọi là cây ảo) sao cho cây này bao gồm:

Toàn bộ các đỉnh nằm trong tập truy vấn.
Các cạnh biểu diễn đường đi giữa mọi cặp đỉnh thuộc tập truy vấn. Những cạnh này có thể được thể hiện dưới dạng các cạnh “nén” (dựa trên ý tưởng tối ưu đã trình bày ở trên).

Tuy nhiên, việc chỉ sử dụng các đỉnh thuộc tập truy vấn là chưa đủ. Khi thực hiện nén cạnh, chúng ta cần thêm những đỉnh đóng vai trò “trung gian”, là điểm giao của nhiều đường đi.

Ví dụ, xem xét hình minh họa sau:

Chúng ta không thể chỉ giữ lại $3$ đỉnh $a, b, c$ trong cây ảo. Thay vào đó, cần phải có đỉnh $m$ để kết nối $a, b,$ và $c$.

Điều này đặt ra một câu hỏi mới: số lượng đỉnh tối thiểu cần thiết trong cây ảo (những đỉnh “quan trọng”) là bao nhiêu?

Đáp án là ít hơn $2k$.

Trước hết, tập hợp các đỉnh “quan trọng” này chắc chắn phải chứa $k$ đỉnh ban đầu của truy vấn. Ngoài ra, chúng còn phải bao gồm các đỉnh là tổ tiên chung gần nhất (LCA) của ít nhất một cặp đỉnh bất kỳ trong tập truy vấn.

Chúng ta sẽ sắp xếp lại các đỉnh $a$ theo thứ tự duyệt DFS (Depth First Search). Sau đó, ta thêm vào tập hợp các đỉnh “quan trọng” này các đỉnh là tổ tiên chung gần nhất (LCA) của $k-1$ cặp đỉnh kề nhau $(a_i, a_{i+1})$ (với mọi $1 \leq i < k$). Cuối cùng, loại bỏ các đỉnh bị trùng lặp. Tập hợp đỉnh thu được chính là những đỉnh cần thiết để xây dựng cây mới.

Bây giờ, chúng ta cần chứng minh rằng với mọi cặp đỉnh bất kỳ thuộc tập truy vấn ban đầu, LCA của chúng đều có mặt trong danh sách các đỉnh “quan trọng” vừa được xây dựng. Nếu điều này đúng, tất cả các cạnh cần thiết (đại diện cho các đường đi) sẽ được biểu diễn trong cây ảo dưới dạng các cạnh “nén”.

Chứng Minh: Sự Tồn Tại Của LCA Cho Mọi Cặp Đỉnh Trong Danh Sách

Sắp xếp lại các đỉnh theo thứ tự duyệt DFS.
Ta sử dụng các quy ước sau:
- $u, v$ là hai đỉnh bất kỳ trong danh sách các đỉnh “quan trọng”.
- $T_a$ ký hiệu cây con có gốc là đỉnh $a$.
- Đỉnh $u$ có thứ tự duyệt DFS nhỏ hơn đỉnh $v$.
- $w=LCA(u, v)$ là tổ tiên chung gần nhất của $u$ và $v$.
- $T_c$ được gọi là cây con trực tiếp của $T_p$ nếu và chỉ nếu tồn tại cạnh nối trực tiếp $(p, c)$ và $c$ là một nút trong $T_p$.
Xét một vài trường hợp sau:
- Trường hợp $u$ là tổ tiên của $v$ (hoặc ngược lại). Điều này luôn được đảm bảo bởi cách xây dựng tập đỉnh “quan trọng” của chúng ta.
- Trường hợp $u$ và $v$ là hai đỉnh kề nhau trong danh sách các đỉnh “quan trọng” đã sắp xếp. Điều này cũng luôn được đảm bảo bởi thuật toán.
- Xét cây con $T_w$ (gốc là $w = LCA(u,v)$):
  - Nếu có nhiều hơn $2$ (tức là $>2$) cây con trực tiếp của $T_w$ mà mỗi cây con này chứa ít nhất $1$ đỉnh thuộc danh sách các đỉnh “quan trọng”, thì chắc chắn $w$ sẽ nằm trong tập hợp các đỉnh “quan trọng”. (Điều này là do ta chỉ cần lấy $LCA$ của đỉnh cuối cùng trong một cây con trực tiếp và đỉnh đầu tiên trong cây con trực tiếp liền kề mà DFS duyệt tới, thì LCA đó chính là $w$).
  - Trong hình minh họa, các đỉnh được đặt tên là những đỉnh có trong danh sách “quan trọng”. Giả sử DFS duyệt qua các cây con 1, 2, rồi 3. Ta thấy rằng đỉnh $x$ (đỉnh cuối trong cây con thứ hai) sẽ kề với đỉnh $y$ (đỉnh đầu trong cây con thứ ba) trong danh sách đã sắp xếp. Do đó, $w = LCA(x,y)$ sẽ có mặt trong tập hợp các đỉnh “quan trọng” của chúng ta.
  - Nhận xét này luôn đúng vì đỉnh cuối cùng được duyệt trong một cây con (theo thứ tự DFS) chắc chắn sẽ kề với đỉnh đầu tiên được duyệt trong cây con kế tiếp (theo thứ tự DFS).
  - Nếu có đúng $2$ cây con trực tiếp của $T_w$ thỏa mãn điều kiện (mỗi cây con chứa ít nhất một đỉnh quan trọng, ví dụ cây con chứa $u$ và cây con chứa $v$), thì hiển nhiên, $w = LCA(u,v)$ chính là LCA của đỉnh cuối cùng trong cây con chứa $u$ và đỉnh đầu tiên trong cây con chứa $v$. Do đó, tính đúng đắn của việc xây dựng tập đỉnh “quan trọng” đã được chứng minh.

Xây Dựng Các Cạnh Cho Cây Ảo

Tiếp theo, chúng ta sẽ tiến hành xây dựng các cạnh cho cây ảo.

Sau khi đã xác định được đầy đủ tập hợp các đỉnh cần thiết (các đỉnh “quan trọng”), chúng ta lại một lần nữa sắp xếp chúng theo thứ tự duyệt DFS.

Dựa vào thứ tự duyệt DFS và thông tin từ Duyệt Euler trên cây gốc, chúng ta sẽ “khôi phục” lại các cạnh cho cây ảo.

Giả sử sau khi sắp xếp, ta có danh sách các đỉnh “quan trọng” là $r_1, r_2, r_3, …r_q$. Để thuận tiện cho việc xây dựng cạnh, ta cần chọn một đỉnh làm gốc cho cây ảo. Lựa chọn đơn giản và hiệu quả nhất là chọn đỉnh có thứ tự duyệt DFS sớm nhất, tức là đỉnh $r_1$.

Công việc tiếp theo là tìm đỉnh cha cho các đỉnh còn lại trong danh sách. Để làm điều này, việc xác định nhánh cây mà mỗi đỉnh thuộc về là rất quan trọng.

Khi quá trình duyệt chuyển từ một nhánh cây, ví dụ $r_1 \rightarrow \cdots \rightarrow r_x \rightarrow \cdots \rightarrow r_j$, sang một nhánh khác, ví dụ $r_1 \rightarrow \cdots \rightarrow r_x \rightarrow \cdots \rightarrow r_i$, chúng ta cần một cấu trúc dữ liệu để lưu giữ thông tin về một phần của nhánh cây đã duyệt trước đó. Cấu trúc phù hợp cho việc này chính là .

Ý tưởng chính là: Ban đầu, của chúng ta chứa đỉnh gốc $r_1$. Sau đó, ta duyệt qua các đỉnh còn lại từ $i = 2, 3, \cdots, q$. Nếu cây con có gốc là đỉnh ở đầu hiện tại không chứa đỉnh $r_i$ (điều này có nghĩa là $r_i$ thuộc một nhánh cây mới so với đỉnh đầu stack), thì ta sẽ liên tục loại bỏ các đỉnh ở đầu cho đến khi điều kiện trên không còn đúng nữa (tức là đỉnh đầu stack trở thành tổ tiên của $r_i$). Sau bước này, đỉnh ở đầu chính là cha trực tiếp của $r_i$ trong cây ảo, và ta sẽ thêm một cạnh nối giữa chúng.

Ví dụ, xét cây và danh sách các đỉnh “quan trọng” $r = [r_1, \cdots, r_x, r_y, r_j, r_i, \cdots]$. Quá trình chuyển từ việc xử lý đỉnh $r_j$ sang $r_i$ diễn ra như sau:

Theo thuật toán đã mô tả, khi đang xét nhánh $r_1 \rightarrow \cdots \rightarrow r_x \rightarrow r_y \rightarrow r_j$, để chuyển sang xử lý nhánh chứa $r_i$, chúng ta sẽ loại bỏ $r_y$ và $r_j$ khỏi stack. Khi đó, $r_x$ sẽ trở thành đỉnh cha trực tiếp của $r_i$ trong cây ảo. Cạnh nối giữa $r_x$ và $r_i$ sẽ có trọng số bằng khoảng cách thực sự giữa chúng trên cây gốc (trong ví dụ này là $3$).

Sau khi đã xây dựng cạnh $(r_x, r_i)$, ta đẩy $r_i$ vào đỉnh và tiếp tục quá trình duyệt danh sách $r$.

Cuối cùng, sau khi đã dựng xong cây ảo với các cạnh và trọng số tương ứng, ta áp dụng lại thuật toán $O(N)$ (đã trình bày ở phần trước, dựa trên việc đếm đóng góp của mỗi cạnh) cho chính cây ảo này. Tuy nhiên, vì cây ảo của chúng ta chỉ có tối đa $2k – 1$ đỉnh, nên độ phức tạp của bước này chỉ còn là $O(k)$.

Mã Nguồn Tham Khảo

#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 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 minigraph[N];
stack 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 Cây Ảo (Virtual Tree)

Tóm tắt các bước xây dựng Cây Ảo:

Sắp xếp các đỉnh truy vấn $a_1, a_2, a_3, …, a_k$ theo thứ tự duyệt DFS trên cây gốc.
Tạo tập hợp các đỉnh “quan trọng” cho cây ảo, bao gồm các đỉnh truy vấn ban đầu và các đỉnh $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 các đỉnh “quan trọng” này theo thứ tự duyệt DFS.
Loại bỏ các đỉnh trùng lặp (rời rạc hóa) trong danh sách.
Xây dựng lại các cạnh của cây ảo bằng cách sử dụng một . Khi duyệt qua các đỉnh “quan trọng” đã sắp xếp, nếu cây con có gốc là đỉnh ở đầu không chứa đỉnh đang xét hiện tại (tức là đã chuyển sang nhánh mới), thì ta sẽ loại bỏ () các đỉnh khỏi stack cho đến khi tìm được tổ tiên chung gần nhất phù hợp.
Thêm cạnh vào cây ảo nối từ đỉnh ở đầu (đỉnh cha) đến đỉnh đang xét (đỉnh con), với trọng số cạnh bằng khoảng cách thực sự giữa hai đỉnh này trên cây gốc.
Độ phức tạp cho mỗi lần xây dựng cây ảo là: $O(k \log n)$ (do sắp xếp và tính LCA).

Dưới đây là một hoạt ảnh minh họa quá trình xây dựng cây ảo (virtual tree):