Virtual/Auxiliary Tree (Cây ảo)

Virtual/Auxiliary Tree (Cây ảo)
Tài liệu tham khảo

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ề:

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}$ (
$với a_{i} \neq a_{j} 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_{k}^{2}

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.

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

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)

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.

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

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).

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

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 :

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

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?

Câu trả lời là nhỏ hơn

2 k

Đầ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 = L C A (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
    $L C A$ 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$ )
    Image Not Showing Possible Reasons
    The image was uploaded to a note which you don't have access to
    The note which the image was originally uploaded to has been deleted
    Learn More →
  - 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} \to \dots \to r_{x} \to \dots \to r_{j}

sang nhánh

r_{1} \to \dots \to r_{x} \to \dots \to 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, \dots, 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}, \dots, r_{x}, r_{y}, r_{j}, r_{i}, \dots]

, ta sẽ chuyển từ

r_{j}

sang

r_{i}

như sau:

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

Theo thuật toán được nêu trên, khi xét nhánh

r_{1} \to \dots \to r_{x} \to r_{y} \to 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

2 k - 1

nút nên độ phức tạp trở thành

O (k)

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}, L C A (a_{1}, a_{2}), L C A (a_{2}, a_{3}), . . ., L C A (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:

Bài tập áp dụng

Codeforces Round 339 (Div. 1) D

Bedao OI Contest 1 - Bài 1 : Đếm cầu

Tài liệu tham khảo

CP Tutorial: Virtual/Auxiliary Tree by Radoslav Dimitrov

Virtual/Auxiliary Tree (Cây ảo)

Giới thiệu

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

Bài toán mở đầu

Hướng tiếp cận: Trâu tất cả các cặp

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

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

Sử dụng cạnh có trọng số

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

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

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

Thuật toán Virtual Tree (Cây ảo)

Bài tập áp dụng

Tài liệu tham khảo

Read more

Train I2427

Training Topics

No_Zone_for_Loser's Math Note