题目描述
如题
样例
import java.util.*;
public class Main {
static int N = 6010;
// happy是快乐度;h是head,指引向一个节点的边链表开头地址;e是一个边的开始;ne是下一条边的地址;
static int[] happy = new int[N], h = new int[N], e = new int[N], ne = new int[N];
static boolean[] isChild = new boolean[N];
static int idx = 0;
static int[][] f = new int[N][2];
static void add (int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
static void dfs(int u) {
f[u][1] = happy[u];
for (int v = h[u]; v != -1; v = ne[v]) {
int from = e[v];
dfs(from);
f[u][1] += f[from][0];
f[u][0] += Math.max(f[from][0], f[from][1]);
}
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Arrays.fill(h, -1);
for (int i = 1; i <= n; i++) happy[i] = sc.nextInt();
for (int i = 1; i <= n - 1; i++) {
int a = sc.nextInt(), b = sc.nextInt();
add(b, a);
isChild[a] = true;
}
int u = 1;
while (u <= n) {
if (!isChild[u]) {
dfs(u);
break;
}
++u;
}
System.out.println(Math.max(f[u][0], f[u][1]));
}
}