作者:
p_c
,
2019-08-11 14:01:20
,
阅读 63
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 6005;
int n;
int happy[maxn];
int h[maxn], e[maxn], ne[maxn], idx;
bool has_father[maxn];
int f[maxn][2];
inline void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
inline void dfs(int u) {
f[u][1] = happy[u];
for(int i = h[u]; i + 1; i = ne[i]) {
int v = e[i];
dfs(v);
f[u][0] += max(f[v][1], f[v][0]);
f[u][1] += f[v][0];
}
}
int main(void) {
scanf("%d", &n);
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i ++) scanf("%d", &happy[i]);
for(int i = 1; i <= n - 1; i ++) {
int a, b; scanf("%d%d", &a, &b);
add(b, a);
has_father[a] = true;
}
int root = 1;
while(has_father[root]) root++;
dfs(root);
printf("%d\n", max(f[root][1], f[root][0]));
return 0;
}