Hướng dẫn giải của Điều chỉnh cây
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Cho một cây nhị phân (mỗi nút có tối đa 2 con) với $n$ nút. Tại mỗi nút $i$ có giá trị ban đầu $a_i$. Ta có thể thực hiện thao tác tăng/giảm 1 đơn vị giá trị của một nút bất kỳ. Yêu cầu tìm số thao tác tối thiểu để biến cây thành một cây 'thỏa mãn': các nút lá phải có giá trị 0 hoặc 1, và giá trị của một nút nội bất kỳ phải bằng tổng giá trị của các nút con của nó. Nút gốc là nút 1.
Các cách tiếp cận
Cách Quy hoạch động với mảng
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
int a[5005];
vector<int> adj[5005];
int dp[5005][2]; // dp[u][s] là chi phí tối thiểu cho cay con u khi u co gia tri s (0 hoac 1)
void dfs(int u, int p) {
bool isLeaf = true;
for (int v : adj[u]) {
if (v != p) {
isLeaf = false;
dfs(v, u);
}
}
if (isLeaf) {
dp[u][0] = abs(a[u] - 0);
dp[u][1] = abs(a[u] - 1);
return;
}
// Neu u co 2 con: trai (v1) va phai (v2)
// Gia tri cua u bat buoc phai bang tong cua 2 con.
// Truong hop: u=0 => ca 2 con deu phai la 0.
// Truong hop: u=1 => 1 trong 2 con la 0, con kia la 1.
int v1 = -1, v2 = -1;
for (int v : adj[u]) {
if (v != p) {
if (v1 == -1) v1 = v;
else v2 = v;
}
}
if (v2 == -1) {
// Chi co 1 con
// u = 0 => con = 0
// u = 1 => con = 1
dp[u][0] = dp[v1][0] + abs(a[u] - 0);
dp[u][1] = dp[v1][1] + abs(a[u] - 1);
} else {
// 2 con
// u = 0 => v1=0, v2=0
dp[u][0] = dp[v1][0] + dp[v2][0] + abs(a[u] - 0);
// u = 1 => (v1=0, v2=1) or (v1=1, v2=0)
int cost1 = dp[v1][0] + dp[v2][1];
int cost2 = dp[v1][1] + dp[v2][0];
dp[u][1] = min(cost1, cost2) + abs(a[u] - 1);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
if (!(cin >> n)) return 0;
for (int i = 1; i <= n; i++) cin >> a[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 << min(dp[1][0], dp[1][1]) << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là cách tiếp cận trực quan nhất. Sử dụng quy hoạch động từ lá lên gốc.
- Nếu nút $u$ là lá: $dp[u][0] = |au - 0|$, $dp[u][1] = |au - 1|$.
- Nếu nút $u$ có một con $v$:
- $dp[u][0] = dp[v][0] + |au - 0|$ (vì nếu $u=0$ thì $v$ cũng phải là 0).
- $dp[u][1] = dp[v][1] + |au - 1|$ (vì nếu $u=1$ thì $v$ cũng phải là 1).
- Nếu nút $u$ có hai con $v1, v2$:
- $dp[u][0] = dp[v1][0] + dp[v2][0] + |au - 0|$ (cả hai con đều 0).
- $dp[u][1] = \min(dp[v1][0] + dp[v2][1], dp[v1][1] + dp[v2][0]) + |au - 1|$ (một con 0, một con 1). Độ phức tạp là $O(n)$ vì mỗi nút được xử lý một lần.
Cách Quy hoạch động với map
#include <bits/stdc++.h>
using namespace std;
int n;
int a[5005];
vector<int> adj[5005];
map<int, int> dp[5005]; // dp[u][val] = chi phí để nút u có giá trị val
void dfs(int u, int p) {
bool isLeaf = true;
for (int v : adj[u]) {
if (v != p) {
isLeaf = false;
dfs(v, u);
}
}
if (isLeaf) {
dp[u][0] = abs(a[u] - 0);
dp[u][1] = abs(a[u] - 1);
return;
}
// Lấy danh sách con
vector<int> children;
for (int v : adj[u]) if (v != p) children.push_back(v);
if (children.size() == 1) {
int v = children[0];
for (auto& [val, cost] : dp[v]) {
int curCost = abs(a[u] - val) + cost;
if (!dp[u].count(val) || curCost < dp[u][val])
dp[u][val] = curCost;
}
} else {
int v1 = children[0], v2 = children[1];
for (auto& [val1, cost1] : dp[v1]) {
for (auto& [val2, cost2] : dp[v2]) {
int val = val1 + val2;
int curCost = abs(a[u] - val) + cost1 + cost2;
if (!dp[u].count(val) || curCost < dp[u][val])
dp[u][val] = curCost;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
if (!(cin >> n)) return 0;
for (int i = 1; i <= n; i++) cin >> a[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);
int ans = 2e9;
for (auto& [val, cost] : dp[1]) ans = min(ans, cost);
cout << ans << endl;
return 0;
}
- Time Complexity: O(n * 2^d)
- Space Complexity: O(n * 2^d)
Cách tiếp cận này linh hoạt hơn, sử dụng map để lưu trữ các khả năng giá trị của nút thay vì chỉ 0 hoặc 1.
- Nút lá: Map chứa {0: chi phí |a-0|}, {1: chi phí |a-1|}.
- Nút cha: Nó kết hợp các map của con. Ví dụ, nếu cha có 2 con, nó duyệt qua mọi cặp (val1, val2) từ 2 map con, tính tổng val = val1 + val2 và cập nhật map của cha.
- Tuy nhiên, giải pháp này chỉ đúng nếu ta giới hạn giá trị của lá là 0 hoặc 1. Nếu không giới hạn, cây có thể có giá trị rất lớn. Nhưng trong bài này, vì lá chỉ được 0 hoặc 1, giá trị của các nút cha sẽ tăng theo cấp số nhân. Với $N=5000$, giải pháp này có thể quá chậm hoặc tràn số nếu không kiểm soát chặt chẽ, nhưng nó thể hiện tư duy quy hoạch động tổng quát hơn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(n) | Quy hoạch động với mảng |
| 2 | O(n * 2^d) | O(n * 2^d) | Quy hoạch động với map |
Bài học kinh nghiệm
- Bài toán có tính chất quy hoạch động trên cây (Tree DP).
- Giá trị của một nút nội phụ thuộc hoàn toàn vào các nút con. Do đó, ta nên xử lý từ lá lên gốc (post-order traversal).
- Đặc điểm của bài toán: Nếu nút $u$ có 2 con, khi đó $u$ phải là 0 hoặc 1. Nếu $u=0$, cả hai con đều 0; nếu $u=1$, một con 0 và một con 1.
- Vì nút lá chỉ được nhận giá trị 0 hoặc 1, nên các nút nội cũng chỉ nhận giá trị 0 hoặc 1. Quy hoạch động chỉ cần xét 2 trường hợp này.
Lỗi thường gặp
- Quên xử lý trường hợp nút chỉ có 1 con (nút nhánh có đúng 1 con).
- Sai logic khi tính cost cho nút có 2 con: Phải thử cả 2 trường hợp (con trai=0, con phải=1) và (con trai=1, con phải=0) rồi lấy min.
- Lỗi thứ tự duyệt cây: Cần duyệt post-order (xử lý con trước, cha sau).
Bình luận