Cấu trúc dữ liệu và Giải thuật Bài 120: Phân rã trọng tâm cây (Centroid Decomposition) - Kỹ thuật chia để trị tối thượng trên cây.

Trong các bài toán xử lý cây, nếu Heavy-Light Decomposition (Bài 119) xuất sắc trong việc giải quyết các truy vấn trên đường đi cố định giữa hai nút $u$ và $v$ , thì nó lại gặp trở ngại lớn trước các bài toán thống kê toàn cục không cố định hai đầu mút, ví dụ:

Đếm số lượng cặp đỉnh $(u, v)$ có khoảng cách đúng bằng $K$ trên cây.
Tìm đường đi có độ dài ngắn nhất thỏa mãn tổng trọng số lớn hơn hoặc bằng $W$ .
Tìm khoảng cách từ một đỉnh bất kỳ đến đỉnh được đánh dấu gần nhất trong một cây liên tục cập nhật trạng thái.

Nếu duyệt qua từng cặp đỉnh bằng DFS/BFS thông thường, chi phí thời gian là $O(N^2)$ . Phân rã trọng tâm cây (Centroid Decomposition) mang tư duy Chia để trị (Divide and Conquer) — tương tự như QuickSort hay MergeSort — áp dụng trực tiếp lên cấu trúc đồ thị cây, giúp giảm độ phức tạp của các bài toán thống kê đường đi xuống mức tối ưu $O(N \log N)$ hoặc $O(N \log^2 N)$ .

1. Định nghĩa và Tính chất của Trọng tâm cây (Tree Centroid)

Cho một cây vô hướng gồm $N$ đỉnh. Một đỉnh $C$ được gọi là Trọng tâm (Centroid) của cây nếu khi loại bỏ đỉnh $C$ (cùng các cạnh nối với nó), kích thước của mọi thành phần liên thông (cây con) còn lại đều không vượt quá $\lfloor N / 2 \rfloor$ :

$\forall T_i \in \text{Components}(T \setminus \{C\}), \quad \vert{}T_i\vert{} \le \left\lfloor \frac{N}{2} \right\rfloor$

Định lý tồn tại trọng tâm

Luôn tồn tại: Bất kỳ cây nào cũng có ít nhất một trọng tâm.
Số lượng tối đa: Một cây có tối đa hai trọng tâm. Nếu có hai trọng tâm, hai đỉnh đó bắt buộc phải kề nhau.
Thuật toán tìm kiếm trong $O(N)$ : Xuất phát từ một đỉnh bất kỳ, ta tính kích thước cây con của tất cả các nút bằng DFS. Sau đó, di chuyển dần sang nút con có kích thước lớn hơn $N / 2$ . Đỉnh đầu tiên không có nút con nào có kích thước $> N / 2$ chính là trọng tâm.

2. Tư tưởng Chia để trị trên Cây (Divide and Conquer)

Mọi đường đi giữa hai đỉnh $u$ và $v$ bất kỳ trên cây rơi vào đúng một trong hai trường hợp:

Đi qua trọng tâm $C$ : Đường đi bao gồm đoạn từ $u$ đến $C$ và từ $C$ đến $v$ (với $u$ và $v$ nằm ở hai nhánh cây con khác nhau của $C$ , hoặc một trong hai đỉnh trùng với $C$ ).
Không đi qua trọng tâm $C$ : Toàn bộ đường đi nằm trọn vẹn bên trong một nhánh cây con duy nhất sau khi cắt bỏ $C$ .

Quy trình chia để trị diễn ra như sau:

Tìm trọng tâm $C$ của cây hiện tại kích thước $N$ .
Tính toán tất cả các đường đi hợp lệ đi qua $C$ .
Loại bỏ $C$ khỏi cây (đánh dấu $C$ đã xử lý).
Đệ quy giải quyết bài toán trên từng thành phần liên thông còn lại.

Do mỗi lần chọn trọng tâm, kích thước của các cây con giảm ít nhất một nửa ( $\vert{}T_i\vert{} \le N / 2$ ), chiều sâu đệ quy tối đa chỉ là $\lfloor \log_2 N \rfloor$ . Nếu chi phí tính toán tại mỗi tầng đệ quy là $O(N)$ , tổng thời gian chạy của toàn bộ thuật toán sẽ là $O(N \log N)$ .

3. Cấu trúc Cây Trọng tâm (Centroid Tree)

Khi liên kết mỗi trọng tâm $C$ với các trọng tâm của các nhánh con được sinh ra từ nó, ta thu được một cấu trúc cây mới gọi là Cây Trọng tâm (Centroid Tree):

Gốc của cây là trọng tâm ban đầu của toàn bộ đồ thị.
Con của mỗi nút là trọng tâm của các thành phần liên thông khi cắt bỏ nút đó.
Chiều cao của Cây Trọng tâm luôn được đảm bảo không vượt quá $O(\log N)$ , bất kể cây ban đầu có bị suy biến thành một đường thẳng dài (dạng danh sách liên kết) hay không.

Cấu trúc này cho phép giải quyết các bài toán cập nhật động (Dynamic Queries) bằng cách leo từ một nút lên đến gốc của Cây Trọng tâm qua tối đa $O(\log N)$ bước.

4. Hiện thực hóa Centroid Decomposition bằng Golang

Bài toán kinh điển: Đếm số lượng cặp đỉnh $(u, v)$ có khoảng cách đúng bằng $K$ trên cây không trọng số.

Đoạn mã dưới đây cài đặt hoàn chỉnh thuật toán tìm Centroid và đệ quy chia để trị bằng Golang:

package main

import (
	"fmt"
)

type CentroidDecomposition struct {
	n       int
	adj     [][]int
	sz      []int
	removed []bool // Đánh dấu các trọng tâm đã bị loại bỏ ở các tầng trước
	k       int
	ans     int64
}

func NewCentroidDecomposition(n, k int) *CentroidDecomposition {
	return &CentroidDecomposition{
		n:       n,
		adj:     make([][]int, n),
		sz:      make([]int, n),
		removed: make([]bool, n),
		k:       k,
		ans:     0,
	}
}

func (cd *CentroidDecomposition) AddEdge(u, v int) {
	cd.adj[u] = append(cd.adj[u], v)
	cd.adj[v] = append(cd.adj[v], u)
}

// 1. Tính kích thước cây con
func (cd *CentroidDecomposition) getSizes(u, p int) int {
	cd.sz[u] = 1
	for _, v := range cd.adj[u] {
		if v != p && !cd.removed[v] {
			cd.sz[u] += cd.getSizes(v, u)
		}
	}
	return cd.sz[u]
}

// 2. Tìm trọng tâm của thành phần liên thông hiện tại
func (cd *CentroidDecomposition) findCentroid(u, p, totalSize int) int {
	for _, v := range cd.adj[u] {
		if v != p && !cd.removed[v] && cd.sz[v] > totalSize/2 {
			return cd.findCentroid(v, u, totalSize)
		}
	}
	return u
}

// 3. Thu thập khoảng cách từ các nút trong nhánh con đến trọng tâm
func (cd *CentroidDecomposition) getDistances(u, p, dist int, distList *[]int) {
	if dist > cd.k {
		return
	}
	*distList = append(*distList, dist)
	for _, v := range cd.adj[u] {
		if v != p && !cd.removed[v] {
			cd.getDistances(v, u, dist+1, distList)
		}
	}
}

// 4. Hàm chia để trị cốt lõi
func (cd *CentroidDecomposition) Decompose(entryNode int) {
	totalSize := cd.getSizes(entryNode, -1)
	c := cd.findCentroid(entryNode, -1, totalSize)

	// Đếm các đường đi đi qua trọng tâm c có độ dài đúng bằng k
	distCount := make(map[int]int)
	distCount[0] = 1 // Đường đi xuất phát từ chính c

	for _, v := range cd.adj[c] {
		if !cd.removed[v] {
			var currentDistList []int
			cd.getDistances(v, c, 1, &currentDistList)

			// Ghép khoảng cách của nhánh hiện tại với các nhánh đã duyệt trước đó
			for _, d := range currentDistList {
				target := cd.k - d
				if count, exists := distCount[target]; exists {
					cd.ans += int64(count)
				}
			}

			// Cập nhật khoảng cách của nhánh hiện tại vào bảng tần suất
			for _, d := range currentDistList {
				distCount[d]++
			}
		}
	}

	// Đánh dấu c đã bị loại bỏ
	cd.removed[c] = true

	// Đệ quy chia để trị tiếp tục cho các cây con còn lại
	for _, v := range cd.adj[c] {
		if !cd.removed[v] {
			cd.Decompose(v)
		}
	}
}

func (cd *CentroidDecomposition) Solve() int64 {
	cd.Decompose(0)
	return cd.ans
}

func main() {
	// Khởi tạo cây gồm 7 đỉnh (0 đến 6)
	// Đồ thị dạng hình sao mở rộng
	n := 7
	k := 2 // Tìm số cặp đỉnh có khoảng cách bằng 2 cạnh
	cd := NewCentroidDecomposition(n, k)

	// Cạnh của cây:
	//       0
	//     / | \
	//    1  2  3
	//   /   |   \
	//  4    5    6
	cd.AddEdge(0, 1)
	cd.AddEdge(0, 2)
	cd.AddEdge(0, 3)
	cd.AddEdge(1, 4)
	cd.AddEdge(2, 5)
	cd.AddEdge(3, 6)

	result := cd.Solve()
	fmt.Printf("Số lượng cặp đỉnh có khoảng cách đúng bằng %d: %d\n", k, result)
	// Các cặp thỏa mãn k = 2:
	// Đi qua 0: (1, 2), (1, 3), (2, 3), (0, 4), (0, 5), (0, 6) -> 6 cặp
}

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

Tối ưu hóa vị trí đặt Trung tâm dữ liệu (Facility Location on Trees): Trong mạng phân phối nội dung có topo dạng cây, đỉnh trọng tâm chính là vị trí đặt Hub/Switch lý tưởng nhất để tổng độ trễ hoặc độ trễ cực đại đến tất cả các nút lá đạt mức tối thiểu.
Hệ thống phân cấp quản lý phân tán: Thiết lập các trạm điều phối trung gian sao cho khi một trạm xảy ra sự cố, quy mô của các phân vùng bị chia cắt luôn nhỏ hơn hoặc bằng 50% toàn bộ hệ thống.
Truy vấn khoảng cách động (Dynamic Nearest Marked Node): Khi kết hợp với cấu trúc Cây Trọng tâm, việc bật/tắt trạng thái của một nút và truy vấn khoảng cách tới nút được bật gần nhất chỉ tiêu tốn $O(\log^2 N)$ hoặc $O(\log N)$ thời gian bằng cách leo dần lên tổ tiên trong Cây Trọng tâm.

cấu trúc dữ liệu