有一棵N个节点的树,节点i的权值为w[i],可以剪掉其中一些枝,使得剩下的树上节点权值之和最大,求最大值。
1<=N<=16000; -1E6<=w[i]<=1E6
分析:题目要求至少要选1个节点,设dp[i]表示以i为根的子树,并且选择i的最大权值和。对于i的每个子节点,可以选或不选。
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<i64> w(n);
for (int i = 0; i < n; i++) {
std::cin >> w[i];
}
std::vector<std::vector<int>> adj(n);
for (int i = 1; i < n; i++) {
int x, y;
std::cin >> x >> y;
x--, y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
std::vector<i64> dp(n);
auto dfs = [&](auto self, int x, int p) -> void {
dp[x] = w[x];
for (auto i : adj[x]) if (i != p) {
self(self, i, x);
dp[x] += std::max(0LL, dp[i]);
}
};
dfs(dfs, 0, 0);
std::cout << *std::max_element(dp.begin(), dp.end()) << "\n";
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--) solve();
return 0;
}
标签:std,子树,最大,luoguP1122,dfs,int,adj,节点,dp
From: https://www.cnblogs.com/chenfy27/p/18523482