算法1
(记忆化搜索) $O(n)$
dfs(node, true)表示选node的最大值, dfs(node,false)表示不选node的最大值, 为了加快速度用记忆化的方式
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int C = 6005;
int hi[C], h[C], ne[C], e[C], idx;
bool has_parent[C];
int dp[C][2];
void add(int x, int y) {
ne[idx] = h[x];
e[idx] = y;
h[x] = idx++;
}
int dfs(int node, bool select) {
if (dp[node][select] != -1) return dp[node][select];
dp[node][1] = hi[node];
dp[node][0] = 0;
for (int i = h[node]; i != -1; i = ne[i]) {
int j = e[i];
dp[node][1] += dfs(j, false);
dp[node][0] += max(dfs(j, true), dfs(j, false));
}
if (select) return dp[node][1];
else return dp[node][0];
}
int main() {
int n;
cin >> n;
memset(h, -1, sizeof h);
memset(dp, -1, sizeof dp);
for (int i = 1; i <= n; i ++) cin >> hi[i];
int root = 1;
for (int i = 1; i <= n - 1; i ++) {
int l, k;
cin >> l >> k;
add(k, l);
has_parent[l] = true;
}
for (int i = 1; i <= n; i ++)
if (has_parent[i] == false) {root = i; break;}
int ans = max(dfs(root, true), dfs(root, false));
cout << ans;
return 0;
}