285. 没有上司的舞会
Ural 大学有 N 名职员,编号为 1∼N。
他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。
每个职员有一个快乐指数,用整数 Hi 给出,其中 1≤i≤N。
现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。
在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。
输入格式 第一行一个整数 N。
接下来 N 行,第 i 行表示 i 号职员的快乐指数 Hi。
接下来 N−1 行,每行输入一对整数 L,K,表示 K 是 L 的直接上司。
输出格式 输出最大的快乐指数。
数据范围 1≤N≤6000, −128≤Hi≤127
输入样例: 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5
输出样例: 5
(下面代码的dp[x][0] 代表的是该节点的参加,1是不参加)
import java.util.Scanner;
import java.util.*;
public class Main {
static int[] h = new int[6001];
static int[][] v = new int[6001][6001];
static Scanner scan = new Scanner(System.in);
static int[][] dp = new int[6001][2];
public static void main(String[] args) {
int N = Integer.valueOf(scan.nextLine());
int t = N;
for (int i = 0; i < N; i++) {
h[i + 1] = Integer.valueOf(scan.nextLine());
}
for (int i = 0; i < N - 1; i++) {
String[] split = scan.nextLine().split(" ");
int l = Integer.valueOf(split[0]);
int k = Integer.valueOf(split[1]);
List son = v.getOrDefault(k, new ArrayList<>());
son.add(l);
v.put(k, son);
v[k][]
}
int p = findPar(N);
dfs(p);
System.out.println(Math.max(dp[p][1], dp[p][0]));
}
private static void dfs(int p) {
dp[p][0] = h[p];
dp[p][1] = 0;
List son = v.get(p);
if (son == null) {
return;
}
for (Integer s: son) {
dfs(s);
dp[p][1] += Math.max(dp[s][0], dp[s][1]);
dp[p][0] += dp[s][1];
}
}
private static int findPar(int N) {
int[] vis = new int[N + 1];
for (Integer k: v.keySet()) {
List son = v.get(k);
for (Integer s: son) {
vis[s] = 1;
}
}
for (int i = 1; i <= N; i++) {
if (vis[i] == 0) {
return i;
}
}
return 1;
}
}



