Cấu trúc dữ liệu và Giải thuật Bài 124: Cây ảo (Virtual Tree / Auxiliary Tree) - Tối ưu hóa truy vấn tập đỉnh con thưa trên cây lớn.

Trong các bài toán xử lý cây phân cấp quy mô lớn ( $N = 10^5$ đến $10^6$ ), nhiều kịch bản thực tế không yêu cầu thao tác trên toàn bộ cấu trúc cây mà chỉ tập trung vào một tập con thưa gồm $K$ đỉnh trọng yếu ( $K \ll N$ ) trong mỗi truy vấn.

Ví dụ kinh điển:

Cho một mạng máy chủ gồm $N$ nút. Mỗi phút hệ thống ghi nhận $K$ máy chủ bị cảnh báo bảo mật. Cần tìm chi phí tối thiểu để ngắt các đường cáp mạng nhằm cô lập toàn bộ $K$ máy chủ này khỏi máy chủ điều khiển trung tâm (gốc).
Tính tổng khoảng cách giữa mọi cặp đỉnh trong tập $K$ đỉnh được chọn.

Nếu mỗi truy vấn ta chạy Quy hoạch động trên cây (Tree DP) hoặc DFS trên toàn bộ cây $N$ đỉnh, độ phức tạp sẽ là $O(Q \cdot N)$ — dẫn đến cạn kiệt tài nguyên xử lý khi $Q$ lớn. Cây ảo (Virtual Tree / Auxiliary Tree) giải quyết triệt để vấn đề này bằng cách trích xuất một cây thu nhỏ chỉ chứa đúng $K$ đỉnh trọng yếu và các Tổ tiên chung gần nhất (LCA) của chúng. Mọi thuật toán sau đó được thực thi trực tiếp trên cây ảo với độ phức tạp phụ thuộc hoàn toàn vào $K$ : $O(K \log K)$ hoặc $O(K)$ , đưa tổng thời gian xử lý $Q$ truy vấn về $O(\sum K \log N)$ .

1. Bản chất và Tính chất cấu trúc của Cây ảo

Cây ảo của một tập đỉnh trọng yếu $S = \{v_1, v_2, \dots, v_k\}$ trên cây gốc $T$ là cây con cảm ứng nhỏ nhất bảo toàn quan hệ tổ tiên - hậu duệ giữa các đỉnh trong $S$ :

Tập đỉnh của Cây ảo ( $V_{\text{virtual}}$ ): Bao gồm tất cả các đỉnh trong $S$ và các đỉnh là $\text{LCA}(u, v)$ của mọi cặp đỉnh $u, v \in S$ .
Khống chế kích thước: Nếu $\vert{}S\vert{} = K$ , số lượng tổ tiên chung gần nhất bổ sung vào tối đa là $K - 1$ . Do đó:

$\vert{}V_{\text{virtual}}\vert{} \le 2K - 1$
$\vert{}E_{\text{virtual}}\vert{} \le 2K - 2$
Cạnh trên Cây ảo: Nối trực tiếp giữa hai đỉnh $u$ và $v$ nếu $u$ là tổ tiên gần nhất của $v$ nằm trong $V_{\text{virtual}}$ . Trọng số của cạnh ảo $(u, v)$ có thể là khoảng cách thực tế giữa $u$ và $v$ trên cây gốc, hoặc giá trị nhỏ nhất của các cạnh trên đường đi từ $u$ đến $v$ .

     Cây gốc (N đỉnh lớn)                  Cây ảo (K đỉnh then chốt: ●)
              (1)                                    (1) [LCA]
             /   \                                  /   \
           (2)   (3)                             (2)●   (4) [LCA]
          /  \      \                                   /   \
        (4)  (5)    (6)                               (7)●  (8)●
       /  \    \
     (7)  (8)  (9)
     (Các nút đen ● là đỉnh cần xử lý)

2. Thuật toán xây dựng Cây ảo bằng Ngăn xếp (Monotonic Stack)

Để dựng Cây ảo trong $O(K \log K)$ , chúng ta sắp xếp các đỉnh theo thứ tự thăm của DFS (DFS entry time - $\text{tin}$ ) và sử dụng một ngăn xếp để duy trì chuỗi tổ tiên hiện tại.

Các bước thực hiện:

Tiền xử lý toàn cục: Chạy DFS một lần trên cây gốc $T$ để tính thời điểm vào $\text{tin}[u]$ , độ sâu $\text{depth}[u]$ và chuẩn bị bảng Binary Lifting để truy vấn $\text{LCA}(u, v)$ trong $O(\log N)$ .
Sắp xếp tập đỉnh: Với mỗi truy vấn chứa tập $S$ , sắp xếp các đỉnh trong $S$ theo $\text{tin}$ tăng dần.
Khởi tạo ngăn xếp: Đưa gốc của cây ảo vào ngăn xếp (thường là gốc của cây lớn hoặc đỉnh đầu tiên).
Duyệt qua từng đỉnh $u \in S$ :
- Tính $lca = \text{LCA}(u, \text{stack.top()})$ .
- Nếu $lca \neq \text{stack.top()}$ : Nghĩa là đường đi hiện tại đã rẽ sang một nhánh mới. Ta lần lượt rút các nút khỏi ngăn xếp và nối cạnh ảo giữa các nút liền kề cho đến khi đỉnh trên cùng của ngăn xếp có $\text{depth} \le \text{depth}[lca]$ .
- Nếu $lca$ chưa có trong ngăn xếp: Đẩy $lca$ vào ngăn xếp và nối cạnh từ $lca$ xuống nút vừa được rút ra gần nhất.
- Đẩy $u$ vào ngăn xếp.
Kết thúc: Nối các cạnh còn lại giữa các đỉnh còn nằm trong ngăn xếp từ trên xuống dưới.

3. Hiện thực hóa Cây ảo bằng Golang

Bài toán minh họa: Cho cây có trọng số gồm $N$ đỉnh. Với mỗi truy vấn gồm $K$ đỉnh nguy hiểm (không chứa đỉnh 1), tìm tổng trọng số cạnh nhỏ nhất cần cắt để cô lập hoàn toàn tất cả $K$ đỉnh này khỏi nút gốc 1.

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
)

const (
	MAXLOG = 20
	INF    = math.MaxInt64 / 4
)

type Edge struct {
	to   int
	cost int64
}

type VEdge struct {
	to      int
	minEdge int64 // Cạnh nhỏ nhất trên đường đi từ cha xuống con ở cây gốc
}

var (
	n          int
	adj        [][]Edge
	tin, tout  []int
	depth      []int
	timer      int
	up         [][]int
	minPath    [][]int64 // minPath[u][i]: cạnh nhỏ nhất từ u lên tổ tiên thứ 2^i
	vAdj       [][]VEdge // Danh sách kề của Cây ảo
	isKey      []bool    // Đánh dấu đỉnh trọng yếu
	vNodes     []int     // Danh sách các đỉnh xuất hiện trong Cây ảo (dùng để reset)
)

func dfsInit(u, p, d int, costToParent int64) {
	depth[u] = d
	up[u][0] = p
	minPath[u][0] = costToParent

	for i := 1; i < MAXLOG; i++ {
		parent := up[u][i-1]
		if parent != 0 {
			up[u][i] = up[parent][i-1]
			minPath[u][i] = min(minPath[u][i-1], minPath[parent][i-1])
		} else {
			up[u][i] = 0
			minPath[u][i] = minPath[u][i-1]
		}
	}

	timer++
	tin[u] = timer

	for _, e := range adj[u] {
		if e.to != p {
			dfsInit(e.to, u, d+1, e.cost)
		}
	}
	tout[u] = timer
}

// Truy vấn LCA và tìm cạnh nhỏ nhất trên đường đi giữa u và v (u là tổ tiên của v)
func getLCAAndMinEdge(u, v int) (int, int64) {
	var minEdge int64 = INF
	if depth[u] > depth[v] {
		u, v = v, u
	}

	diff := depth[v] - depth[u]
	for i := 0; i < MAXLOG; i++ {
		if (diff & (1 << i)) != 0 {
			minEdge = min(minEdge, minPath[v][i])
			v = up[v][i]
		}
	}

	if u == v {
		return u, minEdge
	}

	for i := MAXLOG - 1; i >= 0; i-- {
		if up[u][i] != up[v][i] {
			minEdge = min(minEdge, minPath[u][i])
			minEdge = min(minEdge, minPath[v][i])
			u = up[u][i]
			v = up[v][i]
		}
	}

	minEdge = min(minEdge, minPath[u][0])
	minEdge = min(minEdge, minPath[v][0])
	return up[u][0], minEdge
}

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

// Thêm cạnh có hướng vào Cây ảo và lưu vết để dọn dẹp bộ nhớ
func addVirtualEdge(u, v int) {
	_, minCost := getLCAAndMinEdge(u, v)
	vAdj[u] = append(vAdj[u], VEdge{to: v, minEdge: minCost})
	vNodes = append(vNodes, u, v)
}

// Xây dựng Cây ảo từ tập K đỉnh
func buildVirtualTree(keys []int) int {
	vNodes = vNodes[:0]

	// Sắp xếp các đỉnh theo DFS entry time
	sort.Slice(keys, func(i, j int) bool {
		return tin[keys[i]] < tin[keys[j]]
	})

	stack := []int{1} // Luôn đưa gốc 1 vào cây ảo
	vNodes = append(vNodes, 1)

	for _, u := range keys {
		if u == 1 {
			continue
		}
		top := stack[len(stack)-1]
		lca, _ := getLCAAndMinEdge(u, top)

		if lca != top {
			for len(stack) >= 2 && depth[stack[len(stack)-2]] >= depth[lca] {
				addVirtualEdge(stack[len(stack)-2], stack[len(stack)-1])
				stack = stack[:len(stack)-1]
			}
			if stack[len(stack)-1] != lca {
				addVirtualEdge(lca, stack[len(stack)-1])
				stack[len(stack)-1] = lca
				vNodes = append(vNodes, lca)
			}
		}
		stack = append(stack, u)
	}

	for len(stack) >= 2 {
		addVirtualEdge(stack[len(stack)-2], stack[len(stack)-1])
		stack = stack[:len(stack)-1]
	}

	return 1 // Trả về gốc của Cây ảo
}

// Tree DP trên Cây ảo: O(K)
func dpVirtual(u int) int64 {
	var childrenSum int64 = 0

	for _, e := range vAdj[u] {
		costChild := dpVirtual(e.to)
		childrenSum += min(costChild, e.minEdge)
	}

	if isKey[u] {
		// Nếu u là đỉnh trọng yếu, bắt buộc phải cắt cạnh phía trên nó
		return INF
	}
	return childrenSum
}

func main() {
	// Giả lập cây gốc gồm 6 đỉnh (1 đến 6)
	n = 6
	adj = make([][]Edge, n+1)
	addEdge := func(u, v int, c int64) {
		adj[u] = append(adj[u], Edge{to: v, cost: c})
		adj[v] = append(adj[v], Edge{to: u, cost: c})
	}

	addEdge(1, 2, 5)
	addEdge(1, 3, 10)
	addEdge(2, 4, 3)
	addEdge(2, 5, 8)
	addEdge(3, 6, 2)

	tin = make([]int, n+1)
	tout = make([]int, n+1)
	depth = make([]int, n+1)
	up = make([][]int, n+1)
	minPath = make([][]int64, n+1)
	for i := range up {
		up[i] = make([]int, MAXLOG)
		minPath[i] = make([]int64, MAXLOG)
	}
	vAdj = make([][]VEdge, n+1)
	isKey = make([]bool, n+1)

	timer = 0
	dfsInit(1, 0, 0, INF)

	// Truy vấn mẫu: Cô lập tập các đỉnh {4, 5, 6} khỏi gốc 1
	queryKeys := []int{4, 5, 6}
	for _, k := range queryKeys {
		isKey[k] = true
	}

	// 1. Dựng cây ảo
	root := buildVirtualTree(queryKeys)

	// 2. Chạy DP trên cây ảo
	ans := dpVirtual(root)

	// In kết quả
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()
	fmt.Fprintf(writer, "Chi phí tối thiểu để cô lập tập đỉnh %v khỏi gốc 1: %d\n", queryKeys, ans)

	// 3. Dọn dẹp danh sách kề trong O(K) để sẵn sàng cho truy vấn tiếp theo
	for _, v := range vNodes {
		vAdj[v] = vAdj[v][:0]
		isKey[v] = false
	}
}

4. Phân tích độ phức tạp & Kỹ thuật dọn dẹp bộ nhớ (Clean-up Pattern)

Thao tác	Độ phức tạp thời gian	Ghi chú
Tiền xử lý toàn cục (DFS + LCA)	$O(N \log N)$	Chỉ chạy duy nhất một lần cho toàn bộ chương trình
Sắp xếp tập đỉnh theo tin	$O(K \log K)$	Chi phối thời gian xây dựng cây ảo
Xây dựng cạnh và Ngăn xếp	$O(K \log N)$	Mỗi đỉnh đẩy/rút khỏi stack tối đa 1 lần; tính LCA tốn $O(\log N)$
Duyệt / Quy hoạch động trên Cây ảo	$O(K)$	Cây ảo có không quá $2K$ đỉnh và $2K$ cạnh
Tổng thể cho mỗi truy vấn	$O(K \log N)$	Với $Q$ truy vấn: $O(\sum K \log N)$

Kỹ thuật sống còn: Dọn dẹp trong $O(K)$

Một sai lầm phổ biến khi triển khai Cây ảo là dùng memset hoặc vòng lặp $O(N)$ để xóa danh sách kề vAdj và mảng cờ isKey sau mỗi truy vấn. Điều này làm tăng độ phức tạp lên thành $O(Q \cdot N)$ , phá hủy hoàn toàn lợi ích của Cây ảo.

Giải pháp: Sử dụng mảng động vNodes để ghi nhận lại tất cả các đỉnh thực sự được đưa vào Cây ảo. Khi kết thúc truy vấn, chỉ lặp qua đúng các phần tử trong vNodes để giải phóng vAdj[v] = vAdj[v][:0].

5. Ứng dụng thực tế

Hạ tầng Mạng Phân phối Nội dung (CDN Multicast Tree): Trong mạng phân phối media toàn cầu, khi một luồng phát sóng trực tiếp chỉ có khán giả ở $K$ máy chủ biên, CDN xây dựng một Cây ảo nối gốc (Source) tới $K$ máy chủ đó để tính toán cây truyền phát dữ liệu (Multicast Spanning Tree) tối ưu nhất mà không làm nghẽn băng thông toàn mạng.
Hệ thống Kiểm soát Quyền truy cập Phân tầng (Multi-Tenant RBAC): Đánh giá nhanh cây quyền hạn kế thừa khi kiểm tra xem một người dùng thuộc $K$ nhóm nghiệp vụ có đủ thẩm quyền truy cập một tài nguyên nhạy cảm ở nút gốc hay không.
Phân tích Luồng Dấu vết Hệ thống Microservices (Distributed Trace Filtering): Trong hệ thống có hàng chục nghìn span dịch vụ dạng cây, khi chỉ một vài service kích hoạt cảnh báo trễ, Cây ảo giúp gom và phân tích nguyên nhân gốc (Root Cause Analysis) dọc theo chuỗi gọi phụ thuộc một cách tức thời.

cấu trúc dữ liệu