DP trên cây

Wiki › Thuật toán › Quy hoạch động (DP)

huunguyen · Last updated 3, Tháng 4, 2026, 20:31

DP trên cây là kỹ thuật quy hoạch động trên cấu trúc cây, tính toán các giá trị tại mỗi nút dựa trên kết quả của các nút con. Vì cây không có chu trình, thứ tự tính luôn xác định được thông qua DFS.

Khuôn mẫu chung

void dfs(int u, int parent) {
    // Khởi tạo dp[u]
    dp[u] = base_value;

    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);          // Tính dp[v] trước
        dp[u] = combine(dp[u], dp[v]);  // Cộng gộp kết quả con
    }
    // Xử lý thêm tại u nếu cần
}

Gọi: dfs(root, -1).

Ví dụ 1: Kích thước cây con (Subtree Size)

vector<int> sz(n + 1, 1);

void dfs(int u, int par) {
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

Ví dụ 2: Đường kính cây

Đường kính = đường đi dài nhất giữa hai nút bất kỳ.

int diameter = 0;
vector<int> depth(n + 1, 0);

void dfs(int u, int par) {
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        // Cập nhật đường kính qua u
        diameter = max(diameter, depth[u] + depth[v] + 1);
        depth[u] = max(depth[u], depth[v] + 1);
    }
}

Ví dụ 3: Tập độc lập lớn nhất (Maximum Independent Set)

Bài toán: Chọn tập con các nút sao cho không có hai nút nào liền kề, và tổng trọng số lớn nhất.

Trạng thái:

dp[u][0] = tổng trọng số tối đa trong cây con gốc $u$ , không chọn $u$ .
dp[u][1] = tổng trọng số tối đa trong cây con gốc $u$ , có chọn $u$ .

Công thức chuyển:

d p [u] [0] = \sum_{v \in children (u)} max (d p [v] [0], d p [v] [1])

d p [u] [1] = w [u] + \sum_{v \in children (u)} d p [v] [0]

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> adj[100005];
int w[100005];
long long dp[100005][2];

void dfs(int u, int par) {
    dp[u][0] = 0;
    dp[u][1] = w[u];
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]) << "\n";
}

Ví dụ 4: Re-rooting (Đổi gốc)

Khi bài yêu cầu tính dp[u] cho tất cả các gốc có thể, dùng kỹ thuật re-rooting (đổi gốc) thay vì chạy DFS $n$ lần.

Ý tưởng: Chạy 2 DFS:

DFS từ gốc để tính down[u] (kết quả từ cây con bên dưới).
DFS lần 2 để tính up[u] (kết quả từ phần cây còn lại khi bỏ cây con $u$ ).

Bài toán minh hoạ: Tính tổng khoảng cách từ mỗi nút $u$ đến tất cả nút khác.

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> adj[100005];
long long down[100005]; // tổng khoảng cách từ u xuống cây con
int sz[100005];         // kích thước cây con
long long ans[100005];  // tổng khoảng cách từ u đến mọi nút

void dfs1(int u, int par) {
    sz[u] = 1;
    down[u] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        down[u] += down[v] + sz[v];
    }
}

void dfs2(int u, int par) {
    for (int v : adj[u]) {
        if (v == par) continue;
        // ans[v] = (khoảng cách từ v xuống) + (khoảng cách từ v lên)
        // Khoảng cách lên: ans[u] - down[v] - sz[v] + (n - sz[v])
        ans[v] = ans[u] - sz[v] + (n - sz[v]);
        // Tương đương: ans[v] = ans[u] + n - 2*sz[v]
        dfs2(v, u);
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1, 0);
    ans[1] = down[1];
    dfs2(1, 0);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " \n"[i == n];
}

Ví dụ 5: DP trên cây với ghép cặp (Tree Matching)

Bài toán: Tìm ghép cặp tối đa trên cây (maximum matching).

// dp[u][0] = ghép cặp tối đa trong cây con u, u không được ghép
// dp[u][1] = ghép cặp tối đa trong cây con u, u đã được ghép với 1 con nào đó

void dfs(int u, int par) {
    dp[u][0] = dp[u][1] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        // Nếu u không ghép v: v có thể ghép hoặc không
        int gain = max(dp[v][0], dp[v][1]);
        dp[u][1] = max(dp[u][1],  // u đã ghép với con trước
            dp[u][0] + dp[v][0] + 1);  // ghép u-v ngay bây giờ
        dp[u][0] += gain;
        dp[u][1] = max(dp[u][1], dp[u][0]);  // giữ max
    }
}

DP trên cây có trọng số cạnh

Khi cạnh có trọng số, truyền thêm trọng số vào hàm DFS:

void dfs(int u, int par, long long parentWeight) {
    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        dfs(v, u, w);
        // Sử dụng w trong transition
        dp[u] = max(dp[u], dp[v] + w);
    }
}

Độ phức tạp

Kỹ thuật	Thời gian	Không gian
DP cơ bản (1 DFS)	$O (N)$	$O (N)$
Re-rooting (2 DFS)	$O (N)$	$O (N)$
DP với ghép cây con	$O (N^{2})$ hoặc $O (N \log N)$	$O (N)$

Tổng kết các bài toán DP trên cây thường gặp

Bài toán	Trạng thái
Kích thước cây con	`sz[u]`
Chiều cao / Độ sâu	`depth[u]`
Đường kính cây	`depth[u]` + cập nhật toàn cục
Tập độc lập lớn nhất	`dp[u][0/1]` (chọn / không chọn)
Vertex cover tối thiểu	`dp[u][0/1]`
Ghép cặp tối đa	`dp[u][0/1]` (ghép / không ghép)
Tổng khoảng cách	Re-rooting
Centroid decomposition	Chia cây theo centroid

Bình luận

Không có bình luận tại thời điểm này.