Bài này hướng đi khả quan mà tôi thấy là tham lam:
__Nếu bạn ở 1 đỉnh u thì chi phí tối thiểu là abs(A[u]), nếu chọn đỉnh con của nó thì số thao tác có thể bằng hoặc hơn v:__
__Nhận xét:__
- Nếu A[u] > 0 thì ta cần giảm xuống
- Nếu A[u] < 0 thì ta cần đẩy lên
__Gọi dp:__
- dp[u][0] là số thao tác cần giảm ít nhất để cây con gốc u toàn đỉnh 0
- dp[u][1] là số thao tác cần tăng ít nhất để cây con gốc u toàn đỉnh 0
__Chú ý:__
- dp[u][0] = max(dp[u][0], dp[v][0]) với v là tất cả các đỉnh thuộc cây con gốc u
- dp[u][1] = max(dp[u][1], dp[v][0]) với v là tất cả các đỉnh thuộc cây con gốc u
- Với những lần biến đổi như thế thì gốc sẽ thay đổi giá trị A[u] += dp[v][1] - dp[v][0]
__Lúc này đáp án bài toán sẽ là dp[1][0] + dp[1][1]__
__ĐPT: O(n)__
__Code mẫu:__
#include <bits/stdc++.h>
using namespace std;
constexpr int mx = 1e5;
vector<int> g[mx + 5];
long long A[mx + 5];
long long dp[mx + 5][2];
void dfs(int u, int p){
for (int v : g[u]){
if (v == p) continue;
dfs(v, u);
dp[u][0] = max(dp[u][0], dp[v][0]);
dp[u][1] = max(dp[u][1], dp[v][1]);
}
A[u] += dp[u][1] - dp[u][0];
if (A[u] > 0) dp[u][0] += A[u];
else dp[u][1] += -A[u];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> A[i];
for (int i = 2; i <= n; ++i){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
cout << dp[1][1] + dp[1][0];
}
Sherwin
Created at
1 likes