Quy hoạch động trên cây
Giới thiệu chung
Thông thường, kỹ thuật Quy hoạch động trên cây (DP On Tree) thường được sử dụng trong các bài toán tìm min, max hay tính tổng trên cây. Dạng bài này giống với quy hoạch động thông thường, khi chúng ta cần xác định cấu trúc con tối ưu, tuy nhiên điểm khác biệt là ta sẽ định nghĩa hàm mục tiêu cho từng nút và tính toán dựa trên các nút con của nút đó. Trong bài viết này, chúng ta sẽ cùng tìm hiểu qua 1 số bài toán điển hình của quy hoạch động trên cây.
Bài toán 1 – Làm quen với quy hoạch động trên cây
Cho 1 cây gồm \(N\) đỉnh \((N <=10^5)\), \(N – 1\) cạnh và gốc của cây là \(1\). Với mỗi đỉnh \(u\), hãy đếm số lượng đỉnh nằm trong cây con gốc \(u\).
Ý tưởng
Đặt \(dp_{u}\) là số lượng đỉnh trong cây con gốc \(u\), ban đầu mỗi \(dp_{u}\) đều có giá trị bằng \(1\). Thực hiện dfs trên cây từ đỉnh \(1\), khi xét đến đỉnh \(u\) mà đã xét qua hết các đỉnh con của nó, với mỗi đỉnh con \(v_{i}\) trực tiếp của đỉnh \(u\), ta sẽ thêm tất cả các đỉnh thuộc cây con gốc \(v_{i}\) vào cây con gốc \(u\).
Khi đó ta có công thức truy hồi :
- \(dp_{u}\) \(=\)
Σ \(dp_{v}\) ∀ \(v\) là con trực tiếp của \(u\).
Code mẫu
void dfs(int u , int par){ dp[u] = 1; for(auto v : adj[u]){ if(v == par) continue; dfs(v , u); dp[u] += dp[v]; } }
Độ phức tạp
Ta thực hiện 1 lần dfs trên cây, do đó độ phức tạp thời gian là \(O(n)\).
Bài toán 2 – Hiểu thêm về quy hoạch động trên cây
Cho một cây gồm \(n\) đỉnh \((n <=10^5)\), mỗi đỉnh \(i\) có gắn một trọng số \(a_{i}\) \((a_{i} <=10^9)\). Cần chọn ra một tập các nút trên cây, sao cho với hai nút bất kỳ trong tập không tồn tại cạnh nối giữa chúng và tổng trọng số các nút được chọn là lớn nhất có thể.
Ý tưởng
Đối với các bài toán trên cây mà không cho gốc, trạng thái quy hoạch động thường là đáp án nếu xét một cây con nào đó. Để định nghĩa cây con, cây cần có một gốc nào đó. Ta đặt gốc của cây là đỉnh \(1\) và sẽ dfs từ đỉnh \(1\) để thực hiện quy hoạch động trên cây. Khi xét đến đỉnh \(u\) ta có hai lựa chọn là thêm hoặc không thêm đỉnh \(u\) vào tập. Ta sẽ thực hiện quy hoạch động trên cây như sau:
- Gọi \(f_{u}\) là trọng số lớn nhất của một tập trong cây con gốc \(u\) khi chọn đỉnh \(u\) và \(g_{u}\) là khi không chọn.
- Đối với \(f_{u}\) thì do ta không được chọn các đỉnh con trực tiếp của \(u\) nên công thức truy hồi sẽ là: \(f_{u}\) \(=\) \(a_{u}\) \(+\)
Σ \(g_{v}\) ∀ \(v\) là con trực tiếp của \(u\) - Còn với \(g_{u}\), đỉnh \(u\) không được chọn nên ta có thể chọn các con trực tiếp của \(u\) nên công thức truy hồi là: \(g_{u}\) \(=\)
Σ \(max(g_{v} , f_{v})\) ∀ \(v\) là con trực tiếp của \(u\) - Đáp án của bài toán sẽ là \(max(g_{1} , f_{1})\).
Code mẫu
#include<bits/stdc++.h> using namespace std; #define int long long #define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define fi first #define se second #define pb push_back #define getbit(x , i) ((x >> i) & 1) typedef pair<int , int> pii; const int inf = 1e18; const int mod = 1e9 + 7; const int maxn = 1e5 + 5; int n; int f[maxn] , g[maxn] , a[maxn]; vector<int> adj[maxn]; void dfs(int u , int par){ f[u] += a[u]; for(auto v : adj[u]){ if(v == par) continue; dfs(v , u); f[u] += g[v]; g[u] += max(f[v] , g[v]); } } main() { faster cin >> n; for(int i = 1 ; i <= n ; ++i) cin >> a[i]; for(int i = 1 ; i <= n - 1 ; ++i){ int u , v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfs(1 , -1); cout << max(f[1] , g[1]); }
Độ phức tạp
Ta thực hiện 1 lần dfs trên cây, do đó độ phức tạp thời gian là \(O(n)\).
Bài toán 3 – Kỹ thuật đảo gốc(reroot) trong quy hoạch động trên cây
Nguồn: CSES – 1133
- Tóm tắt đề: Cho cây gồm \(n\) đỉnh, mỗi cạnh có trọng số là \(1\). Với mỗi đỉnh \(i\) từ \(1\) đến \(n\) hãy in ra tổng khoảng cách từ đỉnh \(i\) đến tất cả các đỉnh còn lại.
Ý tưởng
Ta coi gốc của cây là đỉnh \(1\). Đầu tiên với mỗi đỉnh \(u\), ta sẽ tính tổng khoảng cách từ đỉnh \(u\) tới mọi đỉnh thuộc cây con của nó. Ta có thể quy hoạch động tương tự như bài toán 1. Gọi \(cnt_{u}\) là số lượng đỉnh thuộc cây con gốc \(u\) và \(dp_{u}\) là tổng khoảng cách từ đỉnh \(u\) đến mọi đỉnh thuộc cây con của nó. Khi đó ta công thức truy hồi sẽ là:
- \(cnt_{u}\) \(=\)
Σ \(cnt_{v}\) ∀ \(v\) là con trực tiếp của \(u\) - \(dp_{u}\) \(=\)
Σ \(dp_{v}\) + \(cnt_{v}\) ∀ \(v\) là con trực tiếp của \(u\)
Như vậy kết quả của đỉnh \(1\) là \(dp_{1}\). Vậy nên với mỗi đỉnh \(u\) ta có thể đặt nó làm gốc rồi quy hoạch động trên cây như trên để tính kết quả. Có \(n\) đỉnh như vậy nên độ phức tạp sẽ là \(O(n^2)\)
Cải tiến
Bây giờ ta sẽ sử dụng kỹ thuật đảo gốc để cải tiến. Đầu tiên ta dfs 1 lần để tính qua mọi giá trị \(dp\) của các đỉnh khi gốc là \(1\). Thực hiện dfs thêm một lần nữa, khi xét đến đỉnh \(u\) ta coi \(u\) đang là gốc. Giả sử ta đã tính được \(dp[out]_{u}\) là tổng khoảng cách từ mọi đỉnh nằm ngoài cây con gốc \(u\) tới \(u\). Ban đầu có \(dp[out]_{1}\) \(=\) \(0\). Khi chuẩn bị đi xuống một đỉnh \(v_{i}\) với \(v_i\) là con trực tiếp của \(u\), ta cần tính \(dp[out]_{v_{i}}\) hay nói cách khác là chuyển \(v_{i}\) làm gốc. Ta coi rằng những đỉnh nằm ngoài cây con gốc \(u\) đều đã đến được đỉnh \(u\) với tổng khoảng cách đi được là \(dp[out]_{u}\). Ta cũng coi rằng trong mỗi cây con gốc \(v_{j}\) mà \(j ≠ i\) và \(v_{j}\) là con trực tiếp của đỉnh \(u\), mỗi đỉnh đều đã tập hợp ở \(v_{j}\) với tổng khoảng cách là \(dp_{v_{j}}\). Bây giờ, ta cần tính \(dp[out]_{v_{i}}\) hay nói cách khác là di chuyển các đỉnh đang ở \(u\) và ở \(v_{j}\) tới gốc mới \(v_{i}\).
-
- Đầu tiên ta sẽ di chuyển những đỉnh đang ở các đỉnh \(v_{j}\) tới \(u\). Với mỗi đỉnh chỉ cần đi một lần và có
Σ \(cnt_{v_{j}}\) đỉnh nên tổng khoảng cách di chuyển sẽ làΣ \(cnt_{v_{j}}\) - Sau đó ta cần đưa mọi đỉnh đang đứng ở \(u\) xuống \(v_{i}\), mỗi đỉnh chỉ đi một lần và có \(n\) \(-\) \(cnt_{v_{i}}\) đỉnh nên tổng khoảng cách di chuyển sẽ là \(n\) \(-\) \(cnt_{v_{i}}\)
- Để tính \(dp[out]_{v_{i}}\) ta cần cộng thêm tổng khoảng cách trước đó để các đỉnh đi đến được \(u\) cũng như \(v_{j}\) hay nói cách khác chính là \(dp[out]_{u}\) và
Σ \(dp_{v_{j}}\) - Như vậy, công thức tổng quát để tính với mỗi \(dp[out]_{v_{i}}\) sẽ là:
- \(dp[out]_{v_{i}}\) \(=\) \(dp[out]_{u}\) \(+\) \(n\) \(-\) \(cnt_{v_{i}}\) \(+\)
Σ \(cnt_{v_{j}}\) + \(dp_{v_{j}}\) ∀ \(j ≠ i\)
- \(dp[out]_{v_{i}}\) \(=\) \(dp[out]_{u}\) \(+\) \(n\) \(-\) \(cnt_{v_{i}}\) \(+\)
- Với mỗi đỉnh \(u\), kết quả sẽ là \(dp[out]_{u}\) \(+\) \(dp_{u}\).
Code mẫu
#include<bits/stdc++.h> using namespace std; #define int long long #define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define fi first #define se second #define pb push_back #define getbit(x , i) ((x >> i) & 1) typedef pair<int , int> pii; const int inf = 1e18; const int mod = 1e9 + 7; const int maxn = 2e5 + 5; int n; int dp[maxn] , ans[maxn] , cnt[maxn]; vector<int> adj[maxn]; void dfs(int u , int par){ cnt[u] = 1; for(auto v : adj[u]){ if(v == par) continue; dfs(v , u); cnt[u] += cnt[v]; dp[u] += dp[v] + cnt[v]; } } void dfs1(int u , int par , int dp_out){ ans[u] = dp_out + dp[u]; int sum = 0; for(auto v : adj[u]){ if(v == par) continue; sum += dp[v] + cnt[v]; } for(auto v : adj[u]){ if(v == par) continue; int sum1 = sum - dp[v] - cnt[v]; dfs1(v , u , sum1 + dp_out + (n - cnt[v])); } } main() { faster cin >> n; for(int i = 1 ; i <= n - 1 ; ++i){ int u , v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfs(1 , -1); dfs1(1 , -1 , 0); for(int i = 1 ; i <= n ; ++i) cout << ans[i] << " "; }
Độ phức tạp
Ta chỉ thực hiện 2 lần dfs trên cây, do đó độ phức tạp thời gian là \(O(n)\).
- Đầu tiên ta sẽ di chuyển những đỉnh đang ở các đỉnh \(v_{j}\) tới \(u\). Với mỗi đỉnh chỉ cần đi một lần và có
Luyện tập
Dưới đây là một số bài tập để luyện thêm về quy hoạch động trên cây:
Ngoài ra còn rất nhiều bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều hơn về quy hoạch động trên cây, chấm bài online tại http://oj.codedream.edu.vn
- \(cnt_{u}\) \(=\)
