Cấu trúc dữ liệu và Giải thuật Bài 122: Kỹ thuật DSU trên cây (DSU on Tree / Sack) - Giải quyết bài toán thống kê cây con ngoại tuyến trong $O(N \log N)$.

Trong các bài toán xử lý cây phân cấp, việc thống kê thông tin trên toàn bộ cây con của từng đỉnh (Subtree Queries) là một dạng bài toán thường gặp:

Với mỗi đỉnh $u$ , đếm số lượng màu (hoặc thuộc tính) phân biệt xuất hiện trong cây con gốc $u$ .
Với mỗi đỉnh $u$ , tìm giá trị xuất hiện nhiều lần nhất trong cây con gốc $u$ .
Đếm số cặp đỉnh trong cây con thỏa mãn một điều kiện bitwise hoặc hàm băm nhất định.

Nếu sử dụng DFS thuần túy để thu thập dữ liệu cho từng nút, độ phức tạp sẽ chạm ngưỡng $O(N^2)$ . Nếu dùng cấu trúc dữ liệu lưu trữ động như std::map / std::set kết hợp gộp tập nhỏ vào tập lớn (Small-to-Large Merging), độ phức tạp là $O(N \log^2 N)$ nhưng chi phí cấp phát bộ nhớ động (pointer allocation) và hằng số ẩn là rất lớn. Thuật toán Mo trên cây (Bài 121) xử lý được nhưng tốn $O(N \sqrt{N})$ và đòi hỏi sắp xếp ngoại tuyến phức tạp.

DSU on Tree (hay còn gọi là kỹ thuật Sack - Small-to-Large trên cây) giải quyết toàn bộ các bài toán thống kê cây con ngoại tuyến chỉ trong thời gian $O(N \log N)$ và tiêu tốn đúng $O(N)$ bộ nhớ bổ sung với hằng số thực thi tối ưu.

1. Nguồn gốc tên gọi và Trực giác "Small-to-Large"

Kỹ thuật này được cộng đồng thuật toán gọi là "DSU on Tree" không phải vì nó sử dụng cấu trúc find/union với mảng cha như Disjoint Set Union thông thường, mà vì nó kế thừa tư duy cốt lõi của DSU: Luôn giữ lại dữ liệu của phần tử lớn nhất và gộp các phần tử nhỏ hơn vào đó (tương tự heuristic Union by Rank/Size).

Mấu chốt của kỹ thuật:

Mỗi nút $u$ có thể có nhiều nhánh con. Nhánh có kích thước lớn nhất được gọi là con nặng (Heavy Child); các nhánh còn lại là con nhẹ (Light Child) (tương tự như trong HLD ở Bài 119).
Khi tính toán kết quả cho cây con gốc $u$ , ta có thể tận dụng lại toàn bộ dữ liệu thống kê của nhánh con nặng nhất mà không cần xóa đi rồi tính lại từ đầu.
Dữ liệu của các nhánh con nhẹ chỉ cần tính toán độc lập, lưu kết quả, sau đó xóa sạch để tránh làm ô nhiễm bảng đếm toàn cục. Sau khi nhánh con nặng được duyệt xong, ta mới duyệt lại các con nhẹ một lần nữa để gộp dữ liệu vào nhánh con nặng.

2. Quy trình thuật toán: Cơ chế Keep / Clear

Thuật toán duy trì một mảng tần suất toàn cục (Global Frequency Array) duy nhất có kích thước $O(N)$ .

Bước 1: Tiền xử lý cấu trúc cây (DFS 1)

Tính kích thước cây con $\text{sz}[u]$ và xác định nút con nặng nhất $\text{heavyChild}[u]$ cho mỗi đỉnh.

Bước 2: Duyệt và thống kê (DFS 2: `dfs(u, p, keep)`)

Hàm nhận tham số keep (kiểu boolean) xác định xem dữ liệu của cây con gốc $u$ có cần được giữ lại trong mảng toàn cục sau khi kết thúc hàm hay không:

Duyệt các con nhẹ: Lần lượt gọi đệ quy dfs(v, u, false) cho tất cả các nút con nhẹ $v$ của $u$ . Do keep = false, sau khi tính xong kết quả cho $v$ , toàn bộ đóng góp của cây con $v$ vào mảng tần suất toàn cục sẽ bị xóa sạch (clear).
Duyệt con nặng: Gọi dfs(heavyChild[u], u, true). Do keep = true, toàn bộ dữ liệu của cây con nặng được giữ nguyên trong mảng tần suất.
Gộp nhánh nhẹ và đỉnh $u$ : Duyệt lại các cây con nhẹ của $u$ và chính đỉnh $u$ , nạp các phần tử này vào mảng tần suất toàn cục. Lúc này, mảng toàn cục chứa đầy đủ và chính xác toàn bộ dữ liệu của cây con gốc $u$ .
Trả lời truy vấn: Ghi nhận đáp án cho đỉnh $u$ từ mảng toàn cục vào mảng kết quả ans[u].
Dọn dẹp (nếu cần): Nếu bản thân $u$ là một con nhẹ của cha nó (tức là keep == false), duyệt toàn bộ cây con của $u$ để xóa sạch các giá trị khỏi mảng toàn cục, trả lại trạng thái sạch sẽ cho cha của $u$ .

3. Chứng minh độ phức tạp thời gian $O(N \log N)$

Một đỉnh $x$ chỉ bị duyệt qua và thêm/xóa vào mảng tần suất toàn cục khi nó nằm trong một nhánh con nhẹ của một tổ tiên nào đó đang được gộp vào.

Theo tính chất của Heavy-Light Decomposition:

Mỗi khi đi qua một cạnh nhẹ từ con lên cha, kích thước cây con tăng ít nhất gấp đôi: $\text{sz}[\text{parent}] > 2 \cdot \text{sz}[\text{child}]$ .
Do kích thước cây tối đa là $N$ , trên đường đi từ bất kỳ đỉnh nào lên gốc của cây, đỉnh đó chỉ có thể thuộc về tối đa $\lfloor \log_2 N \rfloor$ nhánh con nhẹ.

Vì mỗi đỉnh chỉ bị thêm và xóa khỏi bảng tần suất tối đa $O(\log N)$ lần, và mỗi thao tác thêm/xóa vào mảng diễn ra trong $O(1)$ , tổng thời gian thực thi của toàn bộ thuật toán được đảm bảo ở mức:

$T(N) = O(N \log N)$

Bộ nhớ sử dụng là $O(N)$ vì chỉ cần một mảng đếm tần suất duy nhất và mảng kích thước cây con.

4. Hiện thực hóa DSU on Tree bằng Golang

Bài toán kinh điển: Cho một cây gồm $N$ đỉnh có gốc tại 0. Mỗi đỉnh $u$ có một màu sắc $C[u]$ . Với mỗi đỉnh $u$ , hãy đếm số lượng màu phân biệt xuất hiện trong cây con gốc $u$ .

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	n          int
	color      []int
	adj        [][]int
	sz         []int
	heavyChild []int
	ans        []int

	// Cấu trúc dữ liệu thống kê toàn cục
	freq     []int
	distinct int
)

// DFS 1: Tính kích thước cây con và xác định con nặng nhất
func dfsInit(u, p int) {
	sz[u] = 1
	heavyChild[u] = -1
	maxSubtree := 0

	for _, v := range adj[u] {
		if v != p {
			dfsInit(v, u)
			sz[u] += sz[v]
			if sz[v] > maxSubtree {
				maxSubtree = sz[v]
				heavyChild[u] = v
			}
		}
	}
}

// Hàm thêm hoặc xóa một đỉnh vào/khỏi mảng tần suất toàn cục
func modify(c, delta int) {
	if delta == 1 {
		if freq[c] == 0 {
			distinct++
		}
		freq[c]++
	} else {
		freq[c]--
		if freq[c] == 0 {
			distinct--
		}
	}
}

// Duyệt cây con của u để nạp hoặc xóa dữ liệu
// bigChild là con nặng cần bỏ qua (vì dữ liệu của nó đã có sẵn trong bảng)
func updateSubtree(u, p, delta, bigChild int) {
	modify(color[u], delta)
	for _, v := range adj[u] {
		if v != p && v != bigChild {
			updateSubtree(v, u, delta, bigChild)
		}
	}
}

// DFS 2: Thuật toán DSU on Tree cốt lõi
func dfsSolve(u, p int, keep bool) {
	// 1. Duyệt tất cả các con nhẹ trước và không giữ lại trạng thái (keep = false)
	for _, v := range adj[u] {
		if v != p && v != heavyChild[u] {
			dfsSolve(v, u, false)
		}
	}

	// 2. Duyệt con nặng nhất và giữ lại trạng thái (keep = true)
	if heavyChild[u] != -1 {
		dfsSolve(heavyChild[u], u, true)
	}

	// 3. Nạp dữ liệu từ các con nhẹ và chính đỉnh u vào bảng tần suất
	// Bỏ qua heavyChild[u] vì dữ liệu của nó đã nằm sẵn trong bảng
	updateSubtree(u, p, 1, heavyChild[u])

	// 4. Lưu lại kết quả thống kê cho đỉnh u
	ans[u] = distinct

	// 5. Nếu không giữ trạng thái (u là con nhẹ của cha nó), xóa sạch toàn bộ cây con u
	if !keep {
		updateSubtree(u, p, -1, -1)
	}
}

func main() {
	// Khởi tạo cây mẫu gồm 7 đỉnh (0 đến 6)
	// Màu sắc tương ứng của từng đỉnh
	color = []int{1, 2, 2, 3, 1, 2, 3}
	n = len(color)

	adj = make([][]int, n)
	addEdge := func(u, v int) {
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	// Cấu trúc cây:
	//         0 (màu 1)
	//       /   \
	//   1 (màu 2) 2 (màu 2)
	//    /   \        \
	// 3 (3)  4 (1)    5 (2)
	//                 /
	//               6 (3)
	addEdge(0, 1)
	addEdge(0, 2)
	addEdge(1, 3)
	addEdge(1, 4)
	addEdge(2, 5)
	addEdge(5, 6)

	sz = make([]int, n)
	heavyChild = make([]int, n)
	ans = make([]int, n)

	// Tìm giá trị màu lớn nhất để cấp phát bảng tần suất
	maxColor := 0
	for _, c := range color {
		if c > maxColor {
			maxColor = c
		}
	}
	freq = make([]int, maxColor+1)
	distinct = 0

	// Bước 1: Tính kích thước cây con
	dfsInit(0, -1)

	// Bước 2: Chạy DSU on Tree bắt đầu từ gốc (giữ lại kết quả gốc: keep = true)
	dfsSolve(0, -1, true)

	// In kết quả
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()
	fmt.Fprintln(writer, "Số lượng màu phân biệt trong cây con của từng đỉnh:")
	for i := 0; i < n; i++ {
		fmt.Fprintf(writer, "Đỉnh %d: %d màu phân biệt\n", i, ans[i])
	}
}

5. So sánh DSU on Tree với các kỹ thuật tương đương

Tiêu chí	DSU on Tree (Sack)	Small-to-Large (map / set)	Segment Tree Merge	Mo's Algorithm on Trees
Độ phức tạp thời gian	$O(N \log N)$	$O(N \log^2 N)$	$O(N \log N)$	$O(N \sqrt{N})$
Độ phức tạp bộ nhớ	$O(N)$	$O(N)$	$O(N \log N)$	$O(N)$
Hằng số thực thi	Cực nhỏ (truy cập mảng liên tục)	Lớn (cấp phát cây đỏ đen / nút con trỏ)	Trung bình (cấp phát nút động)	Lớn (hai con trỏ + sắp xếp khối)
Tính chất bài toán	Chỉ áp dụng cho cây con (Subtree)	Cây con	Cây con (có thể hỗ trợ trực tuyến)	Đường đi ( $u \to v$ ) hoặc cây con
Độ phức tạp cài đặt	Ngắn gọn, dễ debug	Rất ngắn gọn	Phức tạp hơn	Dài, cần Euler Tour + LCA

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

Phân tích cơ cấu tổ chức & Quyền hạn phân cấp: Thống kê số lượng kỹ năng phân biệt hoặc tổng ngân sách dự án mà các bộ phận cấp dưới quản lý trong sơ đồ doanh nghiệp phân tầng.
Tối ưu hóa trình biên dịch (AST Analysis): Đếm số biến duy nhất, hàm nội bộ hoặc kiểm tra phạm vi (scope checking) trong cây cú pháp trừu tượng (Abstract Syntax Tree) khi biên dịch ngôn ngữ lập trình.
Hệ sinh thái mạng phân phối: Tính toán độ đa dạng của các loại mặt hàng tồn kho thuộc các kho vệ tinh phụ thuộc vào một kho trung chuyển tổng.

cấu trúc dữ liệu