算法
(树形DP) $O(n)$
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 6010;
int n;
int h[N],e[N],ne[N],idx;
int happy[N];
int f[N][2];
bool has_father[N];
void add(int a,int b)
{
e[idx] = b, ne[idx] = h[a],h[a] = idx++;
}
void dfs(int u)
{
f[u][1] = happy[u];//选择u节点的话就要加上他的happy值
for(int i = h[u]; i != -1; i = ne[i]) //遍历u的每个子节点
{
int j = e[i];//取得子节点的编号
dfs(j);
f[u][1] += f[j][0];
f[u][0] += max(f[j][0],f[j][1]);
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> happy[i];
memset(h,-1, sizeof h);
for(int i = 0; i < n - 1; i++)
{
int a,b;
cin >> a >> b;
add(b,a);
has_father[a] = true;
}
int root = 1;
while(has_father[root]) root++; //找到根节点
dfs(root);
cout << max(f[root][0],f[root][1]);
return 0;
}