Nghiên cứu và thực hành Dynamic Programming trên cấu trúc cây

Cấu trúc cây là nền tảng quan trọng trong nhiều bài toán tối ưu hóa và xử lý đồ thị. Khi kết hợp với Dynamic Programming (DP), chúng ta có thể giải quyết hiệu quả các bài toán liên quan đến đường đi, phân bố trọng lượng, lựa chọn nút độc lập, và quy hoạch có ràng buộc. Bài viết này tổng hợp các mẫu DP trên cây thường gặp, phân tích logic chuyển trạng thái và trình bày các triển khai mã nguồn được tối ưu hóa.

1. Duyệt cây và thu thập thuộc tính cơ bản

Trước khi áp dụng các kỹ thuật DP phức tạp, việc tính toán các thuộc tính cơ bản như độ sâu, kích thước nhánh và thứ tự duyệt là bước chuẩn bị không thể thiếu. Một hàm duyệt depth-first đơn giản có thể đồng thời xác định độ sâu của từng đỉnh, đếm số lượng đỉnh theo tính chẵn lẻ của độ sâu, và ước lượng khoảng thời gian truy cập (DFS order) cho từng nhánh.

Đối với bài toán yêu cầu tìm độ sâu cực đại hoặc phân bố đỉnh theo độ sâu, ta chỉ cần duy trì biến toàn cục hoặc mảng đếm. Nếu cần xác định thứ tự thăm cực tiểu hoặc cực đại cho một đỉnh, kết quả lần lượt tương đương với độ sâu của đỉnh đó và công thức tính dựa trên kích thước nhánh.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
int depth[MAXN], subSize[MAXN], parityCount[2];
int minDfn[MAXN], maxDfn[MAXN];

void collectTreeProperties(int u, int parent) {
    depth[u] = depth[parent] + 1;
    subSize[u] = 1;
    parityCount[depth[u] % 2]++;
    
    minDfn[u] = depth[u];
    maxDfn[u] = 1; // Placeholder, will be updated after traversal

    for (int v : adj[u]) {
        if (v == parent) continue;
        collectTreeProperties(v, u);
        subSize[u] += subSize[v];
        maxDfn[u] += subSize[v];
    }
}

void solve() {
    int n; cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    depth[0] = 0;
    collectTreeProperties(1, 0);
    
    for (int i = 1; i <= n; ++i) {
        cout << minDfn[i] << ' ' << (n - subSize[i] + 1) << '\n';
    }
}

2. Tính đường kính cây bằng DP

Đường kính của một cây là độ dài đường đi dài nhất giữa hai đỉnh bất kỳ. Thay vì thực hiện hai lần duyệt tìm điểm xa nhất, ta có thể sử dụng DP trên cây bằng cách lưu trữ hai giá trị tại mỗi nút: độ dài đường đi dài nhất và thứ hai xuất phát từ nút đó xuống các nhánh con.

Khi xử lý một nút gốc tạm thời, ta duyệt qua tất cả con trực tiếp. Đối với mỗi con, ta lấy giá trị đường đi dài nhất từ nhánh con cộng với trọng số cạnh, sau đó cập nhật vào hai biến lưu trữ cực đại của nút hiện tại. Tổng của hai giá trị cực đại này chính là ứng viên cho đường kính cây.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
vector<pair<int, int>> adj[MAXN];
int longest1[MAXN], longest2[MAXN];
int diameter = 0;

void computeDiameter(int u, int parent) {
    longest1[u] = longest2[u] = 0;
    for (auto [v, w] : adj[u]) {
        if (v == parent) continue;
        computeDiameter(v, u);
        
        int candidate = longest1[v] + w;
        if (candidate > longest1[u]) {
            longest2[u] = longest1[u];
            longest1[u] = candidate;
        } else if (candidate > longest2[u]) {
            longest2[u] = candidate;
        }
    }
    diameter = max(diameter, longest1[u] + longest2[u]);
}

3. Kỹ thuật thay đổi gốc (Rerooting DP)

Nhiều bài toán yêu cầu tính toán một đại lượng cho mọi đỉnh khi đỉnh đó đóng vai trò là gốc, chẳng hạn như tổng khoảng cách đến tất cả các đỉnh khác. Kỹ thuật Rerooting DP giải quyết vấn đề này bằng hai lần duyệt: lần đầu tính toán giá trị ban đầu khi chọn một đỉnh cố định làm gốc, lần thứ hai lan truyền giá trị này sang các đỉnh lân cận theo công thức chuyển gốc.

Giả sử `distSum[u]` là tổng khoảng cách khi gốc là `u`. Khi di chuyển gốc từ `u` sang con `v`, các nút trong nhánh `v` sẽ tiến lại gần hơn 1 đơn vị, trong khi các nút còn lại sẽ xa đi 1 đơn vị. Công thức cập nhật là `distSum[v] = distSum[u] + N - 2 * subSize[v]`.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
long long distSum[MAXN];
int subSize[MAXN];
int N;

void calculateSubtreeSize(int u, int parent) {
    subSize[u] = 1;
    for (int v : adj[u]) {
        if (v == parent) continue;
        calculateSubtreeSize(v, u);
        subSize[u] += subSize[v];
    }
}

void rerootDP(int u, int parent) {
    for (int v : adj[u]) {
        if (v == parent) continue;
        distSum[v] = distSum[u] - subSize[v] + (N - subSize[v]);
        rerootDP(v, u);
    }
}

void solve() {
    cin >> N;
    for (int i = 1; i < N; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    calculateSubtreeSize(1, 0);
    for (int i = 1; i <= N; ++i) distSum[1] += depthFromRoot(1, i); // Initial BFS/DFS omitted for brevity
    rerootDP(1, 0);
}

4. Bài toán chọn nút độc lập và phủ đỉnh

Đây là nhóm bài toán kinh điển yêu cầu lựa chọn tập hợp các đỉnh thỏa mãn ràng buộc lân cận, đồng thời tối đa hóa trọng số hoặc tối thiểu hóa số lượng chọn. Trạng thái DP thường có dạng `memo[u][0/1]`, trong đó chiều thứ hai biểu thị việc đỉnh `u` được chọn hay không.

Nếu đỉnh `u` được chọn, tất cả con trực tiếp bắt buộc không được chọn. Ngược lại, nếu `u` không được chọn, mỗi con có thể tự do ở trạng thái chọn hoặc không, ta lấy giá trị tối ưu nhất từ từng nhánh con. Quá trình này được thực hiện một cách đệ quy từ lá lên gốc.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
int weight[MAXN];
long long memo[MAXN][2]; // 0: not selected, 1: selected

void independentSetDP(int u, int parent) {
    memo[u][1] = weight[u];
    memo[u][0] = 0;
    
    for (int v : adj[u]) {
        if (v == parent) continue;
        independentSetDP(v, u);
        
        memo[u][1] += memo[v][0];
        memo[u][0] += max(memo[v][0], memo[v][1]);
    }
}

// For minimization problems (e.g., vertex cover), swap max/min and adjust base cases accordingly.

5. Quy hoạch kiểu Backpack trên cây

Khi bài toán yêu cầu phân bổ một nguồn lực giới hạn (số cạnh giữ lại, số môn học, dung lượng tải) trên cây, ta áp dụng tư tưởng bài toán Knapsack kết hợp với duyệt cây. State thường là `memo[u][k]` lưu giá trị tối ưu khi dành `k` đơn vị tài nguyên cho nhánh gốc `u`.

Truyền trạng thái từ con lên cha đòi hỏi vòng lặp lồng nhau. Vòng ngoài duyệt từng con, vòng trong cập nhật mảng `memo` của cha bằng cách gộp kết quả từ con. Để tránh sử dụng lại tài nguyên của cùng một con nhiều lần trong cùng một bước gộp, vòng lặp theo số lượng tài nguyên phải chạy ngược (từ lớn đến nhỏ).

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 1e5 + 5, MAXK = 105;
vector<int> adj[MAXN];
int courseScore[MAXN];
long long memo[MAXN][MAXK];
int limit;

void treeKnapsack(int u, int parent) {
    memo[u][1] = courseScore[u]; // Must select current node to select children
    int currentCap = 1;
    
    for (int v : adj[u]) {
        if (v == parent) continue;
        treeKnapsack(v, u);
        
        for (int i = currentCap; i >= 1; --i) {
            for (int j = 1; j <= limit - i; ++j) {
                if (i + j <= limit) {
                    memo[u][i + j] = max(memo[u][i + j], memo[u][i] + memo[v][j]);
                }
            }
        }
        currentCap += limit;
        if (currentCap > limit) currentCap = limit;
    }
}

6. Xử lý đồ thị có chu trình trước khi DP

Dynamic Programming trên cây yêu cầu cấu trúc dữ liệu phải là cây hoặc DAG. Nếu đầu vào là đồ thị có hướng chứa chu trình, ta cần áp dụng thuật toán tìm Thành phần liên thông mạnh (SCC) như Tarjan hoặc Kosaraju để thu gọn đồ thị. Mỗi SCC sẽ được nén thành một siêu đỉnh, tổng hợp trọng số và giá trị từ các đỉnh thành viên ban đầu.

Sau khi thu gọn, đồ thị mới chắc chắn là một rừng cây (forest). Ta có thể thêm một đỉnh gốc ảo kết nối đến tất cả các thành phần không có đỉnh vào, sau đó áp dụng chính xác quy trình Knapsack trên cây đã trình bày ở phần trước. Việc này đảm bảo tính đúng đắn của DP khi xử lý các ràng buộc phụ thuộc vòng tròn.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 505;
vector<int> adj[MAXN], condensedAdj[MAXN];
int dfn[MAXN], lowLink[MAXN], visited[MAXN], componentId[MAXN];
int compWeight[MAXN], compValue[MAXN], inDegree[MAXN];
long long memo[MAXN][MAXN];
stack<int> stk;
int timer, compCount, N, capacity;

void tarjanSCC(int u) {
    dfn[u] = lowLink[u] = ++timer;
    visited[u] = true;
    stk.push(u);
    
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjanSCC(v);
            lowLink[u] = min(lowLink[u], lowLink[v]);
        } else if (visited[v]) {
            lowLink[u] = min(lowLink[u], dfn[v]);
        }
    }
    
    if (dfn[u] == lowLink[u]) {
        compCount++;
        while (true) {
            int v = stk.top(); stk.pop();
            visited[v] = false;
            componentId[v] = compCount;
            compWeight[compCount] += initialWeight[v];
            compValue[compCount] += initialValue[v];
            if (v == u) break;
        }
    }
}

void sccKnapsackDP(int u, int parent) {
    for (int k = compWeight[u]; k <= capacity; ++k) memo[u][k] = compValue[u];
    for (int v : condensedAdj[u]) {
        if (v == parent) continue;
        sccKnapsackDP(v, u);
        for (int i = capacity - compWeight[u]; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                memo[u][i + compWeight[u]] = max(memo[u][i + compWeight[u]], memo[u][i + compWeight[u] - j] + memo[v][j]);
            }
        }
    }
}

7. Tính đóng góp cạnh và tối ưu trạng thái

Trong một số bài toán nâng cao, giá trị mục tiêu không chỉ phụ thuộc vào các nút được chọn mà còn phụ thuộc vào trọng số của các cạnh được "kích hoạt" bởi sự phân bố trạng thái ở hai đầu. Khi đó, công thức tính đóng góp của một cạnh phụ thuộc vào số lượng nút có màu/trạng thái nhất định ở hai phía khi cắt bỏ cạnh đó.

Giả sử cạnh `(u, v)` có trọng số `w`, và ta đã chọn `j` nút trạng thái A trong nhánh `v`, trong tổng số `B` nút trạng thái A cần chọn cho toàn bộ cây. Số cặp nút cùng trạng thái đi qua cạnh này sẽ là tích của số nút trạng thái A ở hai bên nhân với số nút trạng thái B ở hai bên. Khi cập nhật DP, ta cộng thêm giá trị đóng góp này vào tổng kết quả. Việc xử lý trạng thái `j = 0` cần được thực hiện riêng biệt để đảm bảo vòng lặp cập nhật hoạt động chính xác cả khi duyệt ngược.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 2005;
vector<pair<int, int>> adj[MAXN];
long long memo[MAXN][MAXN];
int subSize[MAXN];
int N, targetBlack;

void treeColoringDP(int u, int parent) {
    subSize[u] = 1;
    memo[u][0] = memo[u][1] = 0;
    
    for (auto [v, w] : adj[u]) {
        if (v == parent) continue;
        treeColoringDP(v, u);
        subSize[u] += subSize[v];
        
        for (int i = min(targetBlack, subSize[u]); i >= 0; --i) {
            // Base case for j = 0
            if (memo[u][i] > -1e18) {
                memo[u][i] += memo[v][0] + (long long)subSize[v] * (N - targetBlack - subSize[v]) * w;
            }
            
            for (int j = 1; j <= min(i, subSize[v]); ++j) {
                if (memo[u][i - j] < -1e18 || memo[v][j] < -1e18) continue;
                
                long long crossPairs = (long long)j * (targetBlack - j) + 
                                      (long long)(subSize[v] - j) * (N - targetBlack - subSize[v] + j);
                
                memo[u][i] = max(memo[u][i], memo[u][i - j] + memo[v][j] + crossPairs * w);
            }
        }
    }
}