Cấu trúc dữ liệu và Giải thuật Bài 121: Thuật toán Mo trên cây (Mo's Algorithm on Trees) - Xử lý truy vấn đoạn ngoại tuyến kết hợp Euler Tour.

Khi xử lý các bài toán truy vấn đường đi trên cây như tính tổng hay tìm giá trị lớn nhất, các kỹ thuật như Heavy-Light Decomposition (HLD) hay Binary Lifting giải quyết hiệu quả trong thời gian $O(\log^2 N)$ hoặc $O(\log N)$ nhờ tính chất kết hợp (associative) của phép toán. Tuy nhiên, khi đối mặt với các truy vấn thống kê phức tạp không có tính chất đại số gộp được, ví dụ:

• Đếm số lượng giá trị phân biệt trên đường đi từ đỉnh $u$ đến đỉnh $v$.

• Tìm phần tử có tần suất xuất hiện nhiều nhất (Mode) trên đường đi $u \to v$.

Các cấu trúc dữ liệu như Segment Tree hay HLD trở nên cồng kềnh hoặc bế tắc. Trên mảng 1D, Thuật toán Mo (Mo's Algorithm) giải quyết các bài toán này ngoại tuyến (offline) trong thời gian $O((N + Q)\sqrt{N})$. Bằng cách kết hợp Euler Tour (Kỹ thuật trải phẳng cây) với cơ chế Toggle (Bật/Tắt đỉnh), chúng ta có thể mở rộng thuật toán Mo lên cấu trúc cây vô hướng một cách tối ưu.

1. Kỹ thuật trải phẳng cây bằng Euler Tour

Để áp dụng thuật toán Mo, cây phải được chuyển đổi thành một mảng 1 chiều. Thay vì dùng Euler Tour chỉ ghi nhận thời điểm thăm đỉnh một lần, thuật toán Mo trên cây yêu cầu ghi nhận đỉnh hai lần:

1. Thời điểm bắt đầu bước vào thăm cây con gốc $u$: $\text{tin}[u]$.

2. Thời điểm kết thúc việc thăm toàn bộ cây con gốc $u$ và quay lui: $\text{tout}[u]$.

Mảng trải phẳng euler sẽ có kích thước đúng bằng $2N$. Mỗi đỉnh $u$ xuất hiện đúng hai lần tại hai chỉ số $\text{tin}[u]$ và $\text{tout}[u]$.

2. Ánh xạ đường đi $u \to v$ thành đoạn mảng $[L, R]$

Giả sử không mất tính tổng quát, xét $\text{tin}[u] \le \text{tin}[v]$. Gọi $p = \text{LCA}(u, v)$ là tổ tiên chung gần nhất của $u$ và $v$. Có hai trường hợp xảy ra:

Trường hợp 1: $u$ là tổ tiên của $v$ ($p = u$)

Đường đi từ $u$ đến $v$ là một đường đi xuôi dọc theo nhánh cây.

• Khoảng truy vấn tương ứng trên mảng euler là:

  $$[L, R] = [\text{tin}[u], \text{tin}[v]]$$

• Quy tắc xuất hiện:

  • Những đỉnh thuộc đường đi từ $u$ đến $v$ chỉ xuất hiện đúng 1 lần trong khoảng $[\text{tin}[u], \text{tin}[v]]$.

  • Những đỉnh thuộc các nhánh con rẽ nhánh ra ngoài rồi quay lại đều xuất hiện đúng 2 lần (đã vào và đã ra).

Trường hợp 2: $u$ không phải là tổ tiên của $v$ ($p \neq u$)

Đường đi từ $u$ đến $v$ phải đi vòng qua tổ tiên chung $p$.

• Khoảng truy vấn tương ứng trên mảng euler là:

  $$[L, R] = [\text{tout}[u], \text{tin}[v]]$$

• Quy tắc xuất hiện:

  • Những đỉnh xuất hiện đúng 1 lần trong khoảng này nằm trên đường đi từ $u$ đến $v$ (ngoại trừ đỉnh $p$).

  • Những đỉnh xuất hiện 2 lần nằm ngoài đường đi.

  • Điểm cần lưu ý về LCA: Đỉnh $p = \text{LCA}(u, v)$ có $\text{tin}[p] < \text{tout}[u]$ và $\text{tout}[p] > \text{tin}[v]$, nghĩa là $p$ hoàn toàn không xuất hiện trong đoạn $[\text{tout}[u], \text{tin}[v]]$. Vì vậy, sau khi tính toán đoạn $[L, R]$, ta phải tạm thời thêm giá trị của đỉnh $p$ vào cấu trúc dữ liệu để lấy kết quả, rồi gỡ bỏ $p$ ra trước khi chuyển sang truy vấn tiếp theo.

3. Cơ chế Toggle (Bật / Tắt đỉnh)

Trong thuật toán Mo thông thường, khi hai con trỏ curL và curR di chuyển, ta gọi hàm add() hoặc remove().

Trên cây, mỗi khi con trỏ quét qua một vị trí chứa đỉnh $x$:

• Nếu đỉnh $x$ chưa có trong đường đi (tần suất trong cửa sổ hiện tại là lẻ): Ta bật $x$ (gọi hàm add(x)).

• Nếu đỉnh $x$ đã có trong đường đi (tần suất trong cửa sổ chạm mốc 2, tức chẵn): Ta tắt $x$ (gọi hàm remove(x)).

Duy trì một mảng boolean inPath[x] để theo dõi trạng thái:

Go

func toggle(node int) {
    if inPath[node] {
        removeNode(node)
    } else {
        addNode(node)
    }
    inPath[node] = !inPath[node]
}

4. Hiện thực hóa Mo's Algorithm on Trees bằng Golang

Bài toán minh họa: Cho cây gồm $N$ đỉnh, mỗi đỉnh có một trọng số màu. Xử lý $Q$ truy vấn ngoại tuyến, mỗi truy vấn yêu cầu đếm số lượng màu phân biệt trên đường đi từ $u$ đến $v$.

Go

package main

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

const MAXLOG = 20

type Query struct {
	id     int
	l, r   int
	lca    int
	block  int
}

var (
	n, q        int
	color       []int
	adj         [][]int
	tin, tout   []int
	euler       []int
	timer       int
	up          [][]int
	depth       []int
	
	// Trạng thái Mo
	inPath      []bool
	freqColor   map[int]int
	distinct    int
	ans         []int
)

func dfs(u, p, d int) {
	depth[u] = d
	up[u][0] = p
	for i := 1; i < MAXLOG; i++ {
		if up[u][i-1] != -1 {
			up[u][i] = up[up[u][i-1]][i-1]
		} else {
			up[u][i] = -1
		}
	}

	tin[u] = timer
	euler[timer] = u
	timer++

	for _, v := range adj[u] {
		if v != p {
			dfs(v, u, d+1)
		}
	}

	tout[u] = timer
	euler[timer] = u
	timer++
}

func getLCA(u, v int) int {
	if depth[u] < depth[v] {
		u, v = v, u
	}
	diff := depth[u] - depth[v]
	for i := 0; i < MAXLOG; i++ {
		if (diff & (1 << i)) != 0 {
			u = up[u][i]
		}
	}
	if u == v {
		return u
	}
	for i := MAXLOG - 1; i >= 0; i-- {
		if up[u][i] != up[v][i] {
			u = up[u][i]
			v = up[v][i]
		}
	}
	return up[u][0]
}

func addNode(u int) {
	c := color[u]
	if freqColor[c] == 0 {
		distinct++
	}
	freqColor[c]++
}

func removeNode(u int) {
	c := color[u]
	freqColor[c]--
	if freqColor[c] == 0 {
		distinct--
	}
}

func toggle(u int) {
	if inPath[u] {
		removeNode(u)
	} else {
		addNode(u)
	}
	inPath[u] = !inPath[u]
}

func main() {
	// Giả lập dữ liệu đồ thị mẫu gồm 6 đỉnh
	// Màu sắc của từng đỉnh (0 đến 5)
	color = []int{1, 2, 1, 3, 2, 4}
	n = len(color)

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

	addEdge(0, 1)
	addEdge(0, 2)
	addEdge(1, 3)
	addEdge(1, 4)
	addEdge(2, 5)

	// Khởi tạo các mảng phụ trợ
	tin = make([]int, n)
	tout = make([]int, n)
	euler = make([]int, 2*n)
	depth = make([]int, n)
	up = make([][]int, n)
	for i := range up {
		up[i] = make([]int, MAXLOG)
	}

	timer = 0
	dfs(0, -1, 0)

	// Danh sách các truy vấn (u, v)
	rawQueries := [][2]int{
		{3, 5}, // Đường đi: 3 -> 1 -> 0 -> 2 -> 5 (Màu: 3, 2, 1, 1, 4 -> 4 màu phân biệt)
		{3, 4}, // Đường đi: 3 -> 1 -> 4 (Màu: 3, 2, 2 -> 2 màu phân biệt)
		{1, 2}, // Đường đi: 1 -> 0 -> 2 (Màu: 2, 1, 1 -> 2 màu phân biệt)
	}
	q = len(rawQueries)

	blockSize := int(math.Max(1, float64(2*n)/math.Sqrt(float64(q))))
	queries := make([]Query, q)

	for i, rq := range rawQueries {
		u, v := rq[0], rq[1]
		if tin[u] > tin[v] {
			u, v = v, u
		}
		lca := getLCA(u, v)

		queries[i].id = i
		if lca == u {
			queries[i].l = tin[u]
			queries[i].r = tin[v]
			queries[i].lca = -1
		} else {
			queries[i].l = tout[u]
			queries[i].r = tin[v]
			queries[i].lca = lca
		}
		queries[i].block = queries[i].l / blockSize
	}

	// Sắp xếp các truy vấn theo cấu trúc khối Mo
	sort.Slice(queries, func(i, j int) bool {
		if queries[i].block != queries[j].block {
			return queries[i].block < queries[j].block
		}
		if queries[i].block%2 == 1 {
			return queries[i].r < queries[j].r
		}
		return queries[i].r > queries[j].r
	})

	inPath = make([]bool, n)
	freqColor = make(map[int]int)
	distinct = 0
	ans = make([]int, q)

	curL := 0
	curR := -1

	for _, qry := range queries {
		// Mở rộng hoặc thu hẹp con trỏ
		for curL > qry.l {
			curL--
			toggle(euler[curL])
		}
		for curR < qry.r {
			curR++
			toggle(euler[curR])
		}
		for curL < qry.l {
			toggle(euler[curL])
			curL++
		}
		for curR > qry.r {
			toggle(euler[curR])
			curR--
		}

		// Xử lý tạm thời nút LCA nếu u không phải là tổ tiên của v
		if qry.lca != -1 {
			toggle(qry.lca)
		}

		ans[qry.id] = distinct

		if qry.lca != -1 {
			toggle(qry.lca)
		}
	}

	// In kết quả theo thứ tự truy vấn ban đầu
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()
	fmt.Fprintln(writer, "Kết quả số lượng màu phân biệt trên đường đi:")
	for i, res := range ans {
		fmt.Fprintf(writer, "Truy vấn %d (đường đi %d <-> %d): %d màu phân biệt\n", 
			i+1, rawQueries[i][0], rawQueries[i][1], res)
	}
}

5. Phân tích độ phức tạp & Lưu ý thực thi

Tối ưu hóa hằng số (Hilbert Curve): Thay vì sắp xếp theo khối $(L / B, R)$, có thể sắp xếp các cặp $(L, R)$ dựa trên chỉ số đường cong Hilbert để giảm tổng quãng đường di chuyển của hai con trỏ từ $O(N \sqrt{Q})$ xuống hệ số nhỏ hơn đáng kể trong thực tế.Bộ nhớ mảng phẳng: Kích thước mảng euler luôn là $2N$, do đó kích thước khối phải được tính dựa trên $2N$ chứ không phải $N$.