Wiki › Thuật toán › Quy hoạch động (DP) › DP trên cây

DP trên cây

huunguyen Updated Tháng sáu 1, 2026

DP trên cây (tree DP) là kỹ thuật quy hoạch động trên cấu trúc cây, trong đó kết quả tại mỗi đỉnh được tính từ kết quả của các đỉnh con. Nó giải các bài như: kích thước/độ cao cây con, đường kính cây, tập độc lập lớn nhất, ghép cặp tối đa, tổng khoảng cách... Nhờ cây không có chu trình, ta tính được mọi trạng thái chỉ trong một lần DFS — $O (N)$ , thay vì thử mọi tổ hợp $O (2^{N})$ một cách ngây thơ.

Ý tưởng / Trực giác

Điều khiến DP trên cây hoạt động là tính chất cây con độc lập: với một gốc cố định, cây con của một đỉnh $u$ chỉ giao tiếp với phần còn lại của cây qua đúng một cạnh (cạnh nối $u$ với cha của nó). Vì vậy:

Lời giải tối ưu cho cây con gốc $u$ chỉ phụ thuộc vào lời giải tối ưu của các cây con gốc con $v$ của $u$ — đây chính là tính chất bài toán con tối ưu mà mọi DP cần.
Các cây con của hai đỉnh con khác nhau không chồng lấn (không có đỉnh chung), nên ta được phép gộp kết quả của chúng một cách độc lập.

Cây không có chu trình bảo đảm không có vòng phụ thuộc: muốn tính $d p [u]$ chỉ cần $d p [v]$ của các con, mà các con luôn được DFS xử lý xong trước khi quay lại $u$ (hậu thứ tự — post-order). Đó là lý do ta luôn dfs(v) rồi mới gộp vào dp[u].

Khuôn mẫu chung:

void dfs(int u, int parent) {
    dp[u] = base_value;             // trạng thái khởi tạo cho riêng u
    for (int v : adj[u]) {
        if (v == parent) continue;  // tránh quay ngược lên cha
        dfs(v, u);                  // tính dp[v] TRƯỚC (post-order)
        dp[u] = combine(dp[u], dp[v]); // gộp kết quả con vào cha
    }
}
// Gọi: dfs(root, -1);

Khi mỗi đỉnh có nhiều "chế độ" (chọn/không chọn, ghép/không ghép...), ta mở rộng trạng thái thành dp[u][trạng_thái] và viết công thức chuyển cho từng chế độ.

Ví dụ chạy tay: Tập độc lập lớn nhất

Bài toán. Mỗi đỉnh có trọng số $w [u]$ . Chọn một tập đỉnh sao cho không hai đỉnh nào kề nhau, tổng trọng số lớn nhất.

Trạng thái:

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

Chuyển: $d p [u] [0] = \sum_{v \in c o n (u)} max (d p [v] [0], d p [v] [1])$ $d p [u] [1] = w [u] + \sum_{v \in c o n (u)} d p [v] [0]$

Nếu chọn $u$ thì mọi con đều không được chọn (dùng dp[v][0]); nếu không chọn $u$ thì mỗi con tự do chọn cái tốt hơn.

Xét cây sau, gốc là 1, trọng số ghi trong ngoặc:

            1 (10)
           /      \
        2 (5)     3 (8)
        /  \
     4 (4)  5 (3)

DFS đi theo hậu thứ tự, xử lý lá trước. Lá khởi tạo dp[lá][0]=0, dp[lá][1]=w:

đỉnh	thứ tự xử lý	dp[u][0]	dp[u][1]	giải thích
4 (lá)	1	0	4	lá: chọn hay không
5 (lá)	2	0	3	lá
2	3	`max(0,4)+max(0,3)=7`	`5 + 0 + 0 = 5`	gộp con 4 và 5
3 (lá)	4	0	8	lá
1	5	`max(7,5)+max(0,8)=15`	`10 + dp[2][0] + dp[3][0] = 10+7+0=17`	gộp con 2 và 3

Đáp số $= max (d p [1] [0], d p [1] [1]) = max (15, 17) = 17$ (chọn đỉnh 1, 4, 5: $10 + 4 + 3$ ).

Lưu ý tại đỉnh 2: dp[2][1]=5 nhỏ hơn dp[2][0]=7. Nhưng vẫn phải giữ cả hai, vì ở đỉnh 1 khi chọn 1 ta buộc dùng dp[2][0] — không được tự ý lấy max sớm.

Cài đặt đầy đủ:

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

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

void dfs(int u, int par) {
    dp[u][0] = 0;       // không chọn u
    dp[u][1] = w[u];    // chọn u
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);                              // post-order: con xong trước
        dp[u][0] += max(dp[v][0], dp[v][1]);    // u bỏ -> con tự do
        dp[u][1] += dp[v][0];                   // u chọn -> con phải bỏ
    }
}

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";
}

Cài đặt: các dạng thường gặp

Kích thước cây con

int sz[100005];
void dfs(int u, int par) {
    sz[u] = 1;                      // tính chính u
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        sz[u] += sz[v];             // cộng kích thước mọi cây con
    }
}

Đường kính cây (đường đi dài nhất giữa hai đỉnh)

Tại mỗi đỉnh $u$ , đường đi dài nhất đi qua $u$ bằng tổng hai nhánh con sâu nhất. Ta vừa duy trì depth[u] (chiều dài nhánh sâu nhất từ $u$ xuống) vừa cập nhật đáp số toàn cục.

int diameter = 0;
int depth[100005];                  // số CẠNH của nhánh sâu nhất từ u xuống

void dfs(int u, int par) {
    depth[u] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        // ghép nhánh đã có với nhánh mới qua v -> đường đi đi qua u
        diameter = max(diameter, depth[u] + depth[v] + 1);
        depth[u] = max(depth[u], depth[v] + 1);   // cập nhật SAU khi ghép
    }
}

Thứ tự hai dòng cuối rất quan trọng: phải cập nhật diameter (ghép nhánh cũ với nhánh mới) trước khi nâng depth[u], nếu không sẽ ghép một nhánh với chính nó.

Ghép cặp tối đa trên cây (maximum matching)

// dp[u][0] = ghép tối đa trong cây con u, u CHƯA được ghép
// dp[u][1] = ghép tối đa trong cây con u, u ĐÃ ghép với một con
long long dp[100005][2];

void dfs(int u, int par) {
    dp[u][0] = 0;
    dp[u][1] = -1e18;               // ban đầu u chưa thể ở trạng thái đã ghép
    long long sumBest = 0;          // tổng max(dp[v][0],dp[v][1]) của mọi con
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        sumBest += max(dp[v][0], dp[v][1]);
    }
    dp[u][0] = sumBest;             // u không ghép: con tự do
    for (int v : adj[u]) {
        if (v == par) continue;
        // ghép cạnh u-v: con v phải ở trạng thái 0, các con khác tự do
        long long cand = sumBest - max(dp[v][0], dp[v][1]) + dp[v][0] + 1;
        dp[u][1] = max(dp[u][1], cand);
    }
}

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

Truyền trọng số cạnh xuống qua tham số DFS:

vector<pair<int,long long>> adj[100005];   // (đỉnh kề, trọng số cạnh)
void dfs(int u, int par) {
    for (auto [v, wt] : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        dp[u] = max(dp[u], dp[v] + wt);     // dùng wt trong chuyển trạng thái
    }
}

Biến thể: Re-rooting (đổi gốc)

Khi cần kết quả ứng với mọi đỉnh làm gốc (ví dụ: tổng khoảng cách từ mỗi đỉnh tới tất cả đỉnh khác), chạy DFS lại $N$ lần là $O (N^{2})$ . Re-rooting làm trong $O (N)$ bằng hai lượt DFS:

Lượt xuống — tính down[u] = đáp án xét riêng phần cây con bên dưới $u$ , và sz[u].
Lượt lên — từ cha truyền xuống con phần đóng góp của "thế giới phía trên", suy ra đáp án đầy đủ cho mọi đỉnh.

Với bài tổng khoảng cách, công thức chuyển gốc từ $u$ sang con $v$ : khi dời gốc qua cạnh $u - v$ , $s z [v]$ đỉnh (cây con $v$ ) lại gần hơn 1, còn $n - s z [v]$ đỉnh còn lại xa thêm 1:

$a n s [v] = a n s [u] - s z [v] + (n - s z [v]) = a n s [u] + n - 2 s z [v]$

#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 của u
int sz[100005];
long long ans[100005];    // tổng khoảng cách từ u tới MỌI đỉnh

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];   // mỗi đỉnh cây con v xa thêm 1 cạnh
    }
}

void dfs2(int u, int par) {
    for (int v : adj[u]) {
        if (v == par) continue;
        ans[v] = ans[u] + n - 2LL * sz[v];   // chuyển gốc u -> 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];        // gốc 1: đáp án = chính down[1]
    dfs2(1, 0);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " \n"[i == n];
}

Độ phức tạp

Kỹ thuật	Thời gian	Bộ nhớ
DP cơ bản (1 DFS)	$O (N)$	$O (N)$
Re-rooting (2 DFS)	$O (N)$	$O (N)$
DP ghép cây con theo kích thước	$O (N^{2})$	$O (N)$

Thời gian $O (N)$ : mỗi đỉnh được DFS thăm đúng một lần, và mỗi cạnh được duyệt đúng hai lần (một lần mỗi hướng trong danh sách kề). Re-rooting chỉ là thêm một lượt DFS nữa nên vẫn tuyến tính.
Bộ nhớ $O (N)$ : danh sách kề chứa $2 (N - 1)$ phần tử, các mảng dp, sz, depth đều cỡ $N$ . Lưu ý ngăn xếp đệ quy cũng tốn $O (N)$ — với cây hình "chuỗi" (path) độ sâu đệ quy bằng $N$ , có thể tràn stack (xem Lỗi thường gặp).
Dạng $O (N^{2})$ : xuất hiện ở "knapsack trên cây" — gộp dp của cây con như một bài cái túi theo số đỉnh; phân tích cặp đỉnh cho thấy tổng công gộp là $O (N^{2})$ chứ không phải $O (N^{3})$ .

⚠️ Lỗi thường gặp

Quên chặn quay lên cha. Cây lưu bằng danh sách kề vô hướng, nên adj[u] chứa cả cha. Thiếu if (v == parent) continue; sẽ gây đệ quy vô hạn (cha gọi con, con gọi lại cha). Nếu cây có thể có cạnh bội (hai cạnh cùng nối $u$ - $v$ ), kiểm tra theo cha không đủ — khi đó nên đánh dấu visited[].
Tràn số (int vs long long). Tổng trọng số, tổng khoảng cách dễ vượt $2^{31}$ . Với $N = 10^{5}$ và trọng số tới $10^{9}$ , kết quả có thể tới $10^{14}$ . Khai báo dp, ans, down là long long; và nhớ ép kiểu trong biểu thức như 2LL * sz[v] để phép nhân không tràn int.
Lấy max quá sớm, làm hỏng định nghĩa trạng thái. Trong tập độc lập, không được "rút gọn" mỗi con về max(dp[v][0], dp[v][1]) ở cả hai nhánh. Khi cha chọn, con buộc phải dùng dp[v][0]. Gộp nhầm sẽ cho đáp án sai mà vẫn chạy ra số.
Sai thứ tự cập nhật ở đường kính. Phải cập nhật đáp số diameter (ghép nhánh cũ với nhánh mới) trước rồi mới nâng depth[u]. Đảo thứ tự sẽ ghép một nhánh với chính nó, cho đường kính lớn giả.
Tràn ngăn xếp với cây sâu. Cây hình chuỗi $N = 10^{5}$ làm đệ quy sâu $10^{5}$ — nhiều hệ thống stack mặc định ~1–8 MB sẽ tràn (lỗi runtime/RTE khó đoán). Cách xử lý: tăng giới hạn stack, hoặc viết DFS khử đệ quy bằng ngăn xếp tường minh.
Khởi tạo trạng thái "không khả thi" sai. Với những trạng thái ban đầu chưa thể đạt (ví dụ dp[u][1] của ghép cặp khi $u$ chưa có con nào để ghép), phải khởi tạo bằng $- \infty$ (vd -1e18), không bằng 0 — nếu để 0, ta vô tình cho phép một trạng thái không hợp lệ.
Quên trường hợp biên $N = 1$ . Cây một đỉnh không có cạnh; vòng đọc n-1 cạnh phải xử lý đúng khi n-1 = 0. Đáp số khi đó thường là chính trọng số đỉnh (hoặc 0 với bài khoảng cách).

Bài tập luyện

Đường kính cây (treediamtr) — (Intermediate) Tính đường kính bằng một lần DFS duy trì depth[u] và cập nhật đáp số toàn cục — bài nhập môn tree DP.
Tổng khoảng cách từ mỗi đỉnh (treedist2) — (Advanced) Yêu cầu kết quả cho mọi đỉnh làm gốc, luyện đúng kỹ thuật re-rooting hai lượt DFS.
Sơn chuồng (barnpaint) — (Advanced) Tô màu các đỉnh sao cho kề nhau khác màu, mở rộng trạng thái thành dp[u][màu] — luyện DP nhiều trạng thái trên cây.
Bò Lân Cận (nearcows) — (Veteran) DP trên cây kết hợp ràng buộc khoảng cách giữa các đỉnh được chọn, đòi hỏi thiết kế trạng thái cẩn thận.
Sinh Vật Huyền Bí (creatures) — (Expert) Knapsack trên cây: gộp dp cây con như bài cái túi, luyện phân tích độ phức tạp $O (N^{2})$ .
Tổng Khoảng Cách (sumdist) — (Expert) Bài re-rooting nâng cao với khối lượng lớn, củng cố công thức chuyển gốc và xử lý tràn số long long.