题目描述

聚会的最高快乐指数

动态规划

状态
状态表示：f[n][2] 表示选取第n个节点与不选取第n个节点的快乐指数
状态属性：max
状态计算：f[n][0] += max(f[s][0], f[s][1]) 其中 s 表示 节点n 的儿子
f[n][1] += f[s][1] 其中 s 表示 节点n 的儿子
最终递归得到的是根节点的最大结果

存储

idx = 0
void add(int father, int son) { //  头插法 
    e[idx] = son // 存储father儿子节点son
    ne[idx] = h[father] // 将son这个节点放在father指引的链表的头部
    h[father] = idx++ // 某一个father的链表起始元素位置
}

具体代码

import java.util.*;

public class Main {

    static int N = 6010;
    static int[] e = new int[N]; // value 存储的子节点
    static int[] ne = new int[N]; // next 下一个节点的位置
    static int[] h = new int[N]; // 起始元素头
    static int idx = 0;
    static int[][] f = new int[N][2];
    static int[] happy = new int[N];
    static boolean[] hasFather = new boolean[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Arrays.fill(h, -1);
        int n = scanner.nextInt();
        for (int i=1; i<=n; i++) happy[i] = scanner.nextInt();
        for (int i=1; i<n; i++) {
            int son = scanner.nextInt();
            int father = scanner.nextInt();
            hasFather[son] = true;
            add(father, son);
        }

        int root = 1;
        while (hasFather[root]) root++;

        dfs(root);

        System.out.println(Math.max(f[root][0], f[root][1]));
    }

    private static void dfs(int root) {
        f[root][1] = happy[root];

        for (int i=h[root]; i!=-1; i=ne[i]) {
            int j = e[i];
            dfs(j);

            f[root][1] += f[j][0];
            f[root][0] += Math.max(f[j][0], f[j][1]);
        }
    }

    private static void add(int father, int son) {
        e[idx] = son;
        ne[idx] = h[father];
        h[father] = idx++;
    }
}