I. Giới thiệu về Quy hoạch động trên cây

Quy hoạch động trên cây (Dynamic Programming on Trees) là một phương pháp đặc biệt trong quy hoạch động, nhằm giải quyết các bài toán về cây. Trong phương pháp này, mục tiêu là tìm ra công thức truy hồi cho các nút trong cây dựa trên các nút con của chúng. Hàm mục tiêu thường được xác định cho từng nút, và giải pháp được tính toán dựa vào các nút con.

Trước khi bắt đầu, độc giả cần có những kiến thức cơ bản về quy hoạch động, cũng như các thuật toán duyệt đồ thị như DFS và BFS, và hiểu biết về cấu trúc cây.

II. Các bài toán cụ thể trong Quy hoạch động trên cây

Bài toán 1: Lựa chọn nút trên cây để tối đa hóa tổng tiền

Đề bài: Cho một cây T với N đỉnh (N ≤ 10^5), mỗi nút i có lượng tiền c_i. Cần chọn ra một dãy các nút trên cây sao cho không có hai nút kề nhau nào được chọn, và tổng số tiền thu được là lớn nhất.

Nhận xét: Bài toán tương tự như bài toán quy hoạch động trên mảng một chiều. Ta đặt dp_i là tổng lớn nhất thu được từ a_1 đến a_i, với công thức dp_i = max(dp_{i - 2} + a_i, dp_{i - 1}).

Hướng tiếp cận: Đầu tiên, xác định gốc của cây bằng cách bắt đầu từ nút 1 và duyệt cây bằng DFS. Tại mỗi nút u, ta tính kết quả cho bài toán con từ các nút con của nó.

Công thức truy hồi:

• f_u = c_u + ∑g_v (v là con của u): chọn nút u.
• g_u = ∑max(f_v, g_v) (v là con của u): không chọn nút u.

Kết quả cuối cùng sẽ được tính bằng cách lấy max(f_1, g_1).

Độ phức tạp: O(N).

Cài đặt:

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

const int maxn = 1e5 + 10;
int c[maxn], f[maxn], g[maxn];
vect....

Bài toán 2: Tìm cây con có trọng số lớn nhất

Đề bài: Cho cây T với N đỉnh (N ≤ 10^5). Cần xác định cây con có trọng số lớn nhất. Trọng số được tính bằng tổng trọng số của tất cả các cạnh.

Hướng tiếp cận: Ta cần đặt dp_u là trọng số của cây con lớn nhất với gốc là u. Kết quả cuối cùng sẽ là max(dp_u).

Công thức truy hồi: d_pu += dp_u + (dp_{v_i} + c_{u, v_i}); ∀i: 1 ≤ i ≤ N.

Cài đặt:

#include <bits/stdc++.h>
#define int long long
#define task "MaxTree."
#define inf 1e9 + 7
// ...

Bài toán 3: Đường kính của cây

Đề bài: Tính độ dài đường đi dài nhất giữa hai nút bất kỳ trên cây. Độ dài đường này được tính bằng số cạnh đi qua.

Hướng tiếp cận: định nghĩa hai hàm f(x) và g(x) cho mỗi nút x; từ đó tính toán đường kính của cây.

Công thức truy hồi:

• f_u = 1 + max(f_{v_1}, f_{v_2}, ..., f_{v_k})
• g_u = 2 + (2 giá trị lớn nhất trong tập {f_{v_1}, f_{v_2}, ..., f_{v_k}})

Độ phức tạp: O(N log(N)).

Bài toán 4: Tính cây con có P đỉnh với trọng số tối đa

Đề bài: Cho một cây T với N đỉnh. Tìm cây con gồm đúng P đỉnh có tổng trọng số lớn nhất.

Hướng tiếp cận: Sử dụng quy hoạch động để tính trọng số lớn nhất trên cây con.

Công thức truy hồi:

• Tính g_{i,j}
• Tính f_{u,j}

Cài đặt:

void dfs(int u, int par) {
    // ...
}

Bài toán 5: Tối ưu hóa đường đi giữa các đảo

Đề bài: Đất nước Delta gồm N hòn đảo với N-1 tuyến phà. Cần thay thế K tuyến phà bằng cầu để giảm tổng thời gian đi lại giữa các đảo.

Hướng tiếp cận: Tính thời gian di chuyển giảm đi cho từng tuyến, từ đó chọn ra K tuyến phà có chênh lệch lớn nhất để thay thế.

Công thức truy hồi:

• ti = h_v × (N - h_v);
• dp_i = ti × (l_i/VP - l_i/VC).

Cài đặt:

const int maxn = 1e5 + 10;
// ...

III. Kết luận về Quy hoạch động trên cây

Quy hoạch động trên cây là một phương pháp hiệu quả để giải quyết nhiều bài toán trên cấu trúc cây, bao gồm cách đặt gốc, sử dụng DFS và tính toán từ dưới lên trên. Tập trung vào việc tối ưu hóa các nút trong cây và chọn lựa các đỉnh chính xác giúp nâng cao hiệu quả và tối ưu hóa giải pháp cho các bài toán phức tạp.

IV. Tài liệu tham khảo

• Codeforces
• Vnoi
  source: viblo