DP trên cây

DP trên cây, tức là thực hiện DP trên cấu trúc cây. Do cây có tính chất đệ quy vốn có, DP trên cây thường được thực hiện bằng đệ quy.

Cơ bản

Lấy ví dụ sau để giới thiệu quá trình DP trên cây thông thường.

Bài mẫu LuoGu P1352 Bữa tiệc không có sếp

Một trường đại học có \(n\) nhân viên, được đánh số từ \(1 \sim N\). Giữa họ có quan hệ cấp trên - cấp dưới, tức là quan hệ của họ giống như một cây với hiệu trưởng là gốc, nút cha là cấp trên trực tiếp của nút con. Hiện tại có một bữa tiệc kỷ niệm, mỗi khi mời một nhân viên sẽ tăng chỉ số hạnh phúc \(a_i\), tuy nhiên, nếu cấp trên trực tiếp của một nhân viên đã tham dự, thì nhân viên đó nhất quyết không tham dự. Hãy lập trình tính toán, mời những nhân viên nào để tổng chỉ số hạnh phúc là lớn nhất, và cho biết chỉ số hạnh phúc lớn nhất đó.

Ta đặt \(f(i,0/1)\) là đáp án tối ưu của cây con gốc tại \(i\) (giá trị thứ hai là 0 nghĩa là \(i\) không tham dự, 1 nghĩa là \(i\) tham dự).

Với mỗi trạng thái, tồn tại hai quyết định (trong đó \(x\) là con của \(i\)):

• Nếu cấp trên không tham dự, cấp dưới có thể tham dự hoặc không, khi đó \(f(i,0) = \sum\max \{f(x,1),f(x,0)\}\);
• Nếu cấp trên tham dự, cấp dưới đều không tham dự, khi đó \(f(i,1) = \sum{f(x,0)} + a_i\).

Ta có thể dùng DFS, khi quay về cha thì cập nhật đáp án tối ưu của nút hiện tại.

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

struct edge {
  int v, next;
} e[6005];

int head[6005], n, cnt, f[6005][2], ans, is_h[6005], vis[6005];

void addedge(int u, int v) {  // 建图
  e[++cnt].v = v;
  e[cnt].next = head[u];
  head[u] = cnt;
}

void calc(int k) {
  vis[k] = 1;
  for (int i = head[k]; i; i = e[i].next) {  // 枚举该结点的每个子结点
    if (vis[e[i].v]) continue;
    calc(e[i].v);
    f[k][1] += f[e[i].v][0];
    f[k][0] += max(f[e[i].v][0], f[e[i].v][1]);  // 转移方程
  }
  return;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> f[i][1];
  for (int i = 1; i < n; i++) {
    int l, k;
    cin >> l >> k;
    is_h[l] = 1;
    addedge(k, l);
  }
  for (int i = 1; i <= n; i++)
    if (!is_h[i]) {  // 从根结点开始DFS
      calc(i);
      cout << max(f[i][1], f[i][0]);
      return 0;
    }
}

Thông thường, trạng thái DP trên cây là đáp án tối ưu tại nút hiện tại. Trước tiên DFS qua các cây con để lấy đáp án tối ưu, sau đó truyền lên cha để chuyển trạng thái, cuối cùng giá trị tại gốc là đáp án tối ưu cần tìm.

Bài tập

• HDU 2196 Computer

• POJ 1463 Strategic game

• [POI2014]FAR-FarmCraft

Balo trên cây

Bài toán balo trên cây, nói đơn giản là sự kết hợp giữa bài toán balo và DP trên cây.

Bài mẫu LuoGu P2014 CTSC1997 Chọn môn học

Hiện có \(n\) môn học, môn thứ \(i\) có số tín chỉ là \(a_i\), mỗi môn có thể có hoặc không có một môn tiên quyết, nếu có thì phải học xong môn tiên quyết mới được học môn đó.

Một học sinh cần học \(m\) môn, hỏi tổng số tín chỉ lớn nhất có thể đạt được là bao nhiêu.

\(n,m \leq 300\)

Đặc điểm mỗi môn chỉ có tối đa một môn tiên quyết, giống như trong cây có gốc, mỗi nút chỉ có một cha.

Do đó, có thể xây dựng cây dựa trên đặc điểm này, toàn bộ các môn tạo thành một rừng. Để thuận tiện, ta thêm một môn số \(0\) có \(0\) tín chỉ (đánh số là \(0\)), làm tiên quyết cho tất cả các môn không có tiên quyết, như vậy biến rừng thành một cây gốc \(0\).

Đặt \(f(u,i,j)\) là đáp án tối ưu khi xét cây con gốc \(u\), đã duyệt qua \(i\) cây con đầu tiên của \(u\), chọn \(j\) môn.

Quá trình chuyển trạng thái kết hợp DP trên cây và DP balo, ta liệt kê từng con \(v\) của \(u\), đồng thời liệt kê số môn chọn trong cây con \(v\), rồi gộp kết quả cây con vào \(u\).

Gọi số con của \(x\) là \(s_x\), kích thước cây con gốc \(x\) là \(\textit{siz}_x\), có thể viết phương trình chuyển trạng thái:

\[ f(u,i,j)=\max_{v,k \leq j,k \leq \textit{siz}_v} f(u,i-1,j-k)+f(v,s_v,k) \]

Lưu ý các điều kiện giới hạn trong phương trình trên, đảm bảo không truy cập các trạng thái vô nghĩa.

Chiều thứ hai của \(f\) có thể dễ dàng loại bỏ bằng mảng cuộn, lưu ý khi đó cần liệt kê \(j\) ngược lại.

Có thể chứng minh độ phức tạp là \(O(nm)\)¹.

Mã tham khảo

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int f[305][305], s[305], n, m;
vector<int> e[305];

int dfs(int u) {
  int p = 1;
  f[u][1] = s[u];
  for (auto v : e[u]) {
    int siz = dfs(v);
    // 注意下面两重循环的上界和下界
    // 只考虑已经合并过的子树，以及选的课程数超过 m+1 的状态没有意义
    for (int i = min(p, m + 1); i; i--)
      for (int j = 1; j <= siz && i + j <= m + 1; j++)
        f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]);  // 转移方程
    p += siz;
  }
  return p;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int k;
    cin >> k >> s[i];
    e[k].push_back(i);
  }
  dfs(0);
  cout << f[0][m + 1];
  return 0;
}

Bài tập

• 「CTSC1997」Chọn môn học

• 「JSOI2018」Hành động thâm nhập

• 「SDOI2017」Cây táo

• 「Codeforces Round 875 Div. 1」Problem D. Mex Tree

DP đổi gốc trên cây

DP đổi gốc trên cây còn gọi là quét hai lần, thường không chỉ định gốc, và việc thay đổi gốc sẽ ảnh hưởng đến các giá trị như tổng độ sâu con, tổng trọng số, v.v.

Thường cần hai lần DFS, lần đầu để tiền xử lý các thông tin như độ sâu, tổng trọng số, lần hai để chạy DP đổi gốc.

Sau đây là một số ví dụ để làm quen với nội dung này.

Bài mẫu [POI2008]STA-Station

Cho một cây \(n\) đỉnh, hãy tìm một nút làm gốc sao cho tổng độ sâu các nút là lớn nhất.

Giả sử \(u\) là nút hiện tại, \(v\) là con của \(u\). Đầu tiên cần dùng \(s_i\) để biểu diễn số nút trong cây con gốc \(i\), có \(s_u=1+\sum s_v\). Rõ ràng cần một lần DFS để tính tất cả \(s_i\), đây là bước tiền xử lý, ta có tổng số nút trong cây con gốc mỗi nút.

Xét chuyển trạng thái, đây là lúc "đổi gốc". Gọi \(f_u\) là tổng độ sâu các nút khi gốc là \(u\).

Chuyển từ \(f_u\) sang \(f_v\) thể hiện đổi gốc, tức là chuyển từ gốc \(u\) sang gốc \(v\). Khi đổi gốc, các nút trong cây con \(v\) giảm độ sâu đi 1, tổng độ sâu giảm \(s_v\); các nút không thuộc cây con \(v\) tăng độ sâu lên 1, tổng độ sâu tăng \(n-s_v\).

Từ đó có phương trình chuyển trạng thái \(f_v = f_u - s_v + n - s_v=f_u + n - 2 \times s_v\).

Lần DFS thứ hai duyệt toàn bộ cây và chuyển trạng thái \(f_v=f_u + n - 2 \times s_v\), như vậy có thể tính tổng độ sâu với mỗi nút làm gốc. Cuối cùng duyệt qua tất cả các tổng độ sâu để lấy đáp án.

Mã tham khảo

#include <iostream>
using namespace std;

int head[1000010 << 1], tot;
long long n, sz[1000010], dep[1000010];
long long f[1000010];

struct node {
  int to, next;
} e[1000010 << 1];

void add(int u, int v) {  // 建图
  e[++tot] = {v, head[u]};
  head[u] = tot;
}

void dfs(int u, int fa) {  // 预处理dfs
  sz[u] = 1;
  dep[u] = dep[fa] + 1;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v != fa) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

void get_ans(int u, int fa) {  // 第二次dfs换根dp
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (v != fa) {
      f[v] = f[u] - sz[v] * 2 + n;
      get_ans(v, u);
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  int u, v;
  for (int i = 1; i <= n - 1; i++) {
    cin >> u >> v;
    add(u, v);
    add(v, u);
  }
  dfs(1, 1);
  for (int i = 1; i <= n; i++) f[1] += dep[i];
  get_ans(1, 1);
  long long int ans = -1;
  int id;
  for (int i = 1; i <= n; i++) {  // 统计答案
    if (f[i] > ans) {
      ans = f[i];
      id = i;
    }
  }
  cout << id << '\n';
  return 0;
}

Bài tập

• Atcoder Educational DP Contest, Problem V, Subtree

• Educational Codeforces Round 67, Problem E, Tree Painting

• POJ 3585 Accumulation Degree

• [USACO10MAR]Great Cow Gathering G

• CodeForce 708C Centroids

Tài liệu tham khảo & chú thích

---

1. Chứng minh độ phức tạp DP balo hợp nhất cây con - Blog CSDN của LYD729 ↩

---

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:aaron20100919
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply