Cấu trúc dữ liệu và Giải thuật Bài 126: Quy hoạch động động trên cây (Dynamic Tree DP - DDP) - Tối ưu hóa cập nhật trạng thái DP trên cây bằng nhân ma trận và HLD.

Quy hoạch động trên cây (Tree DP) giải quyết nhiều bài toán tối ưu tổ hợp kinh điển trong thời gian tuyến tính $O(N)$, tiêu biểu như bài toán Tập độc lập có trọng số cực đại (Maximum Weight Independent Set - MWIS). Tuy nhiên, các bài toán thực tế thường đòi hỏi xử lý cập nhật trạng thái liên tục: trọng số hoặc chi phí của các đỉnh thay đổi theo thời gian thực ($Q$ truy vấn cập nhật).

Nếu mỗi lần cập nhật trọng số đỉnh, hệ thống chạy lại thuật toán Tree DP từ đầu, tổng thời gian sẽ là $O(Q \cdot N)$ — không thể đáp ứng được các ứng dụng yêu cầu độ trễ thấp. Quy hoạch động động trên cây (Dynamic Tree DP - DDP) giải quyết triệt để bài toán này bằng cách biểu diễn bước chuyển trạng thái DP dưới dạng phép nhân ma trận trên vành bán nhiệt đới (Tropical Semiring) kết hợp với Phân rã cây nặng - nhẹ (HLD) và Cây phân đoạn (Segment Tree), giúp đưa chi phí của mỗi thao tác cập nhật và truy vấn trạng thái toàn cục về mức $O(\log^2 N)$.

1. Biểu diễn trạng thái DP dưới dạng Nhân ma trận Bán nhiệt đới

Xét bài toán Tập độc lập trọng số cực đại (MWIS) trên cây: Với mỗi đỉnh $u$, ta có hai trạng thái quy hoạch động:

• $dp[u][0]$: Trọng số lớn nhất của tập độc lập trong cây con gốc $u$ khi không chọn đỉnh $u$.

• $dp[u][1]$: Trọng số lớn nhất của tập độc lập trong cây con gốc $u$ khi chọn đỉnh $u$ (với trọng số $w[u]$).

Hệ thức truy hồi truyền thống:

$$dp[u][0] = \sum_{v \in \text{children}(u)} \max(dp[v][0], dp[v][1])$$

$$dp[u][1] = w[u] + \sum_{v \in \text{children}(u)} dp[v][0]$$

Tách biệt Nhánh nặng (Heavy) và Nhánh nhẹ (Light)

Gọi $hc(u)$ là con nặng (Heavy Child) của $u$, và $\text{Light}(u)$ là tập các con nhẹ của $u$. Ta định nghĩa hai biến phụ trợ gom toàn bộ đóng góp của các nhánh nhẹ:

$$g[u][0] = \sum_{v \in \text{Light}(u)} \max(dp[v][0], dp[v][1])$$

$$g[u][1] = w[u] + \sum_{v \in \text{Light}(u)} dp[v][0]$$

Khi đó, hệ thức DP của $u$ chỉ còn phụ thuộc trực tiếp vào con nặng $hc(u)$:

$$dp[u][0] = g[u][0] + \max(dp[hc][0], dp[hc][1])$$

$$dp[u][1] = g[u][1] + dp[hc][0]$$

Chuyển đổi sang Ma trận trên Vành $(\max, +)$

Phép nhân ma trận thông thường trên vành số học tiêu chuẩn được định nghĩa bằng $(+, \times)$. Trên Vành bán nhiệt đới $(\max, +)$, phép cộng được thay bằng $\max$ và phép nhân được thay bằng $+$:

$$(A \otimes B)_{i, j} = \max_k (A_{i, k} + B_{k, j})$$

Phần tử không (Zero) là $-\infty$, và phần tử đơn vị (Identity) là ma trận có đường chéo chính bằng $0$ và các vị trí khác bằng $-\infty$.

Chuyển hệ thức DP của $u$ sang dạng nhân vector - ma trận:

$$\begin{bmatrix} dp[u][0] \\ dp[u][1] \end{bmatrix} = \begin{bmatrix} g[u][0] & g[u][0] \\ g[u][1] & -\infty \end{bmatrix} \otimes \begin{bmatrix} dp[hc][0] \\ dp[hc][1] \end{bmatrix}$$

Đặt ma trận chuyển trạng thái của nút $u$ là:

$$M_u = \begin{bmatrix} g[u][0] & g[u][0] \\ g[u][1] & -\infty \end{bmatrix}$$

2. Kiến trúc thuật toán DDP: HLD kết hợp Segment Tree

Do phép nhân ma trận trên vành $(\max, +)$ có tính chất kết hợp ($A \otimes (B \otimes C) = (A \otimes B) \otimes C$), việc tính toán DP dọc theo một chuỗi nặng (Heavy Chain) chuyển thành bài toán tính tích liên tiếp của các ma trận:

$$\begin{bmatrix} dp[\text{head}][0] \\ dp[\text{head}][1] \end{bmatrix} = M_{\text{head}} \otimes M_{\text{next}} \otimes \dots \otimes M_{\text{leaf}} \otimes \begin{bmatrix} 0 \\ 0 \end{bmatrix}$$

Từ đó, kết quả DP tại đỉnh đầu chuỗi nặng $\text{head}$ được suy ra từ tích ma trận toàn chuỗi $P = \prod_{x \in \text{chain}} M_x$:

$$dp[\text{head}][0] = \max(P_{00}, P_{01}), \quad dp[\text{head}][1] = \max(P_{10}, P_{11})$$

Quy trình cập nhật trọng số đỉnh $u$ trong $O(\log^2 N)$

1. Thay đổi trọng số $w[u]$ của đỉnh $u$: Cập nhật lại giá trị $g[u][1]$ và ma trận $M_u$.

2. Cập nhật ma trận $M_u$ vào vị trí tương ứng trên Segment Tree quản lý mảng phẳng HLD.

3. Leo ngược lên gốc cây theo các chuỗi nặng:

   • Tính toán tích ma trận của chuỗi nặng hiện tại để suy ra giá trị DP mới của đỉnh đầu chuỗi $\text{head}$.

   • Nếu $\text{head}$ không phải là gốc cây toàn cục: Nhảy qua cạnh nhẹ lên cha của nó $p = \text{parent}[\text{head}]$.

   • Trừ đi đóng góp cũ của $\text{head}$ vào $g[p]$ và cộng thêm đóng góp mới của $\text{head}$ vào $g[p]$.

   • Cập nhật ma trận $M_p$ mới vào Segment Tree.

   • Gán đỉnh hiện tại là $p$ và tiếp tục lặp lại quá trình leo lên chuỗi nặng tiếp theo.

4. Do đường đi từ $u$ lên gốc chỉ đi qua tối đa $O(\log N)$ chuỗi nặng, và mỗi lần cập nhật/truy vấn trên Segment Tree tốn $O(2^3 \log N)$ thời gian, tổng chi phí cập nhật là $O(\log^2 N)$.

3. Hiện thực hóa Dynamic Tree DP bằng Golang

Chương trình dưới đây cài đặt hoàn chỉnh DDP để giải quyết bài toán Tập độc lập cực đại (MWIS) với khả năng cập nhật trọng số đỉnh động trong $O(\log^2 N)$:

Go

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4

// Matrix 2x2 trên Vành bán nhiệt đới (max, +)
type Matrix [2][2]int64

func NewMatrix() Matrix {
	var m Matrix
	m[0][0], m[0][1] = -INF, -INF
	m[1][0], m[1][1] = -INF, -INF
	return m
}

func Multiply(a, b Matrix) Matrix {
	c := NewMatrix()
	for i := 0; i < 2; i++ {
		for k := 0; k < 2; k++ {
			if a[i][k] <= -INF {
				continue
			}
			for j := 0; j < 2; j++ {
				if b[k][j] <= -INF {
					continue
				}
				val := a[i][k] + b[k][j]
				if val > c[i][j] {
					c[i][j] = val
				}
			}
		}
	}
	return c
}

type DDP struct {
	n          int
	adj        [][]int
	weight     []int64
	parent     []int
	depth      []int
	sz         []int
	heavy      []int
	head       []int
	pos        []int
	revPos     []int
	chainEnd   []int
	curPos     int
	g          [][2]int64
	dp         [][2]int64
	segTree    []Matrix
}

func NewDDP(n int, weights []int64) *DDP {
	return &DDP{
		n:        n,
		adj:      make([][]int, n+1),
		weight:   weights,
		parent:   make([]int, n+1),
		depth:    make([]int, n+1),
		sz:       make([]int, n+1),
		heavy:    make([]int, n+1),
		head:     make([]int, n+1),
		pos:      make([]int, n+1),
		revPos:   make([]int, n+1),
		chainEnd: make([]int, n+1),
		curPos:   0,
		g:        make([][2]int64, n+1),
		dp:       make([][2]int64, n+1),
		segTree:  make([]Matrix, 4*(n+1)),
	}
}

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

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

// DFS 1: Tính toán size, depth, parent và tìm heavy child
func (d *DDP) dfs1(u, p, dep int) {
	d.sz[u] = 1
	d.parent[u] = p
	d.depth[u] = dep
	d.heavy[u] = -1
	maxChild := 0

	for _, v := range d.adj[u] {
		if v != p {
			d.dfs1(v, u, dep+1)
			d.sz[u] += d.sz[v]
			if d.sz[v] > maxChild {
				maxChild = d.sz[v]
				d.heavy[u] = v
			}
		}
	}
}

// DFS 2: Phân rã HLD, tính g-values và DP truyền thống ban đầu
func (d *DDP) dfs2(u, hHead int) {
	d.curPos++
	d.pos[u] = d.curPos
	d.revPos[d.curPos] = u
	d.head[u] = hHead

	d.g[u][0] = 0
	d.g[u][1] = d.weight[u]
	d.dp[u][0] = 0
	d.dp[u][1] = d.weight[u]

	if d.heavy[u] != -1 {
		d.dfs2(d.heavy[u], hHead)
		d.dp[u][0] += max(d.dp[d.heavy[u]][0], d.dp[d.heavy[u]][1])
		d.dp[u][1] += d.dp[d.heavy[u]][0]
	}

	for _, v := range d.adj[u] {
		if v != d.parent[u] && v != d.heavy[u] {
			d.dfs2(v, v)
			d.g[u][0] += max(d.dp[v][0], d.dp[v][1])
			d.g[u][1] += d.dp[v][0]
			d.dp[u][0] += max(d.dp[v][0], d.dp[v][1])
			d.dp[u][1] += d.dp[v][0]
		}
	}
}

// Tạo ma trận M_u cho nút u
func (d *DDP) makeMatrix(u int) Matrix {
	var m Matrix
	m[0][0] = d.g[u][0]
	m[0][1] = d.g[u][0]
	m[1][0] = d.g[u][1]
	m[1][1] = -INF
	return m
}

// Xây dựng Segment Tree trên mảng phẳng HLD
func (d *DDP) buildTree(node, l, r int) {
	if l == r {
		u := d.revPos[l]
		d.segTree[node] = d.makeMatrix(u)
		return
	}
	mid := (l + r) / 2
	d.buildTree(2*node, l, mid)
	d.buildTree(2*node+1, mid+1, r)
	d.segTree[node] = Multiply(d.segTree[2*node], d.segTree[2*node+1])
}

// Cập nhật ma trận tại chỉ số idx trong Segment Tree
func (d *DDP) updateSegTree(node, l, r, idx int, m Matrix) {
	if l == r {
		d.segTree[node] = m
		return
	}
	mid := (l + r) / 2
	if idx <= mid {
		d.updateSegTree(2*node, l, mid, idx, m)
	} else {
		d.updateSegTree(2*node+1, mid+1, r, idx, m)
	}
	d.segTree[node] = Multiply(d.segTree[2*node], d.segTree[2*node+1])
}

// Truy vấn tích ma trận của một đoạn liên tục trên chuỗi nặng
func (d *DDP) querySegTree(node, l, r, ql, qr int) Matrix {
	if ql <= l && r <= qr {
		return d.segTree[node]
	}
	mid := (l + r) / 2
	if qr <= mid {
		return d.querySegTree(2*node, l, mid, ql, qr)
	}
	if ql > mid {
		return d.querySegTree(2*node+1, mid+1, r, ql, qr)
	}
	leftM := d.querySegTree(2*node, l, mid, ql, qr)
	rightM := d.querySegTree(2*node+1, mid+1, r, ql, qr)
	return Multiply(leftM, rightM)
}

// Tìm điểm cuối (sâu nhất) của chuỗi nặng
func (d *DDP) findChainEnd(u int) int {
	curr := u
	for d.heavy[curr] != -1 {
		curr = d.heavy[curr]
	}
	return curr
}

// Lấy DP tại đầu chuỗi nặng
func (d *DDP) getHeadDP(h int) (int64, int64) {
	end := d.chainEnd[h]
	prod := d.querySegTree(1, 1, d.n, d.pos[h], d.pos[end])
	dp0 := max(prod[0][0], prod[0][1])
	dp1 := max(prod[1][0], prod[1][1])
	return dp0, dp1
}

// Cập nhật trọng số của một đỉnh: O(log^2 N)
func (d *DDP) UpdateWeight(u int, newWeight int64) {
	d.g[u][1] += newWeight - d.weight[u]
	d.weight[u] = newWeight

	curr := u
	for curr != 0 {
		h := d.head[curr]
		// 1. Ghi nhận DP cũ của đầu chuỗi nặng
		oldDP0, oldDP1 := d.getHeadDP(h)

		// 2. Cập nhật ma trận tại curr vào Segment Tree
		d.updateSegTree(1, 1, d.n, d.pos[curr], d.makeMatrix(curr))

		// 3. Tính toán DP mới của đầu chuỗi nặng
		newDP0, newDP1 := d.getHeadDP(h)

		// 4. Nhảy lên nút cha của chuỗi nặng và cập nhật g-values
		p := d.parent[h]
		if p == 0 {
			break
		}

		d.g[p][0] += max(newDP0, newDP1) - max(oldDP0, oldDP1)
		d.g[p][1] += newDP0 - oldDP0

		curr = p
	}
}

// Lấy kết quả MWIS của toàn bộ cây
func (d *DDP) QueryMWIS() int64 {
	dp0, dp1 := d.getHeadDP(d.head[1])
	return max(dp0, dp1)
}

func (d *DDP) Init() {
	d.dfs1(1, 0, 0)
	d.dfs2(1, 1)

	// Ghi nhận điểm kết thúc của chuỗi nặng cho mỗi head
	for i := 1; i <= d.n; i++ {
		if d.head[i] == i {
			d.chainEnd[i] = d.findChainEnd(i)
		}
	}

	d.buildTree(1, 1, d.n)
}

func main() {
	// Cây gồm 5 đỉnh (đỉnh 1 đến 5)
	// Trọng số ban đầu: [0, 5, 2, 8, 3, 4]
	weights := []int64{0, 5, 2, 8, 3, 4}
	n := 5
	ddp := NewDDP(n, weights)

	// Các cạnh: (1-2), (1-3), (2-4), (2-5)
	ddp.AddEdge(1, 2)
	ddp.AddEdge(1, 3)
	ddp.AddEdge(2, 4)
	ddp.AddEdge(2, 5)

	ddp.Init()

	// Truy vấn kết quả ban đầu
	fmt.Printf("Trọng số tập độc lập cực đại ban đầu: %d\n", ddp.QueryMWIS())

	// Cập nhật đỉnh 3 tăng vọt từ 8 thành 50
	fmt.Println("Cập nhật: Đỉnh 3 đổi trọng số thành 50...")
	ddp.UpdateWeight(3, 50)
	fmt.Printf("Trọng số MWIS sau khi sửa đỉnh 3: %d\n", ddp.QueryMWIS())

	// Cập nhật đỉnh 1 từ 5 thành 100
	fmt.Println("Cập nhật: Đỉnh 1 đổi trọng số thành 100...")
	ddp.UpdateWeight(1, 100)
	fmt.Printf("Trọng số MWIS sau khi sửa đỉnh 1: %d\n", ddp.QueryMWIS())
}

4. Phân tích độ phức tạp & So sánh kiến trúc

Trong đó $c$ là kích thước ma trận chuyển trạng thái ($c = 2$ đối với bài toán MWIS, $c^3 = 8$ là một hằng số cực nhỏ).

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

• Quy hoạch mạng lưới điện thông minh (Smart Grid Power Flow): Cập nhật công suất tải tiêu thụ của các hộ gia đình hoặc trạm biến áp theo thời gian thực và tự động tính toán lại phương án ngắt mạch tối ưu tức thời.

• Tối ưu hóa cây thư mục & Phân quyền động: Tính toán quyền truy cập kế thừa có điều kiện trên cây phân cấp người dùng khi chính sách tại một phòng ban hoặc một vai trò bị thay đổi đột ngột.

• Định tuyến thời gian thực có ràng buộc năng lực (Dynamic Congestion-aware Routing): Tính toán lộ trình có chi phí rẻ nhất qua cấu trúc mạng khung phân tầng khi thông lượng của các liên kết biến động liên tục.