【树形DP】没有上司的舞会

题目

285. 没有上司的舞会

---

Ural 大学有 $N$ 名职员，编号为 $1 \sim N$ 。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 $H_i$ 给出，其中 $1 \le i \le N$ 。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 $N$ 。

接下来 $N$ 行，第 $i$ 行表示 $i$ 号职员的快乐指数 $H_i$ 。

接下来 $N-1$ 行，每行输入一对整数 $L, K$ ，表示 $K$ 是 $L$ 的直接上司。

输出格式

输出最大的快乐指数。

数据范围

$1 \le N \le 6000$ ,
$-128 \le H_i \le 127$

输入样例：

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例：

5

解题

方法一：动态规划

思路

抽象地理解一下题意：在一棵树中，每个节点都有其权值，在选出的节点不存在边的情况下，选出节点，并使选出节点的权值累和最大，求这个最大的累和权值。

在树中每个节点只与其父节点与子节点相连，从叶节点向根节点考虑时：

• 若选择该节点，那么其每个子节点都不能选，求累和。
• 若不选给节点，那么对每个子节点求选/不选的最大值，求累和。

思维过程：

动态规划：

• 状态定义：

  • $dp[u][0]$ 表示所有从以点 $u$ 为根节点的子树中选择，且不选点 $u$ 的方案的最大的快乐指数。
  • $dp[u][1]$ 表示所有从以点 $u$ 为根节点的子树中选择，且选择点 $u$ 的方案的最大的快乐指数。

• 状态转移方程：（$v$ 是 $u$ 的子节点）

  • $dp[u][0] = \sum {\max(dp[v][0], dp[v][1]})$ 。
  • $dp[u][1] = \sum {dp[v][0]}$ 。

• 初始状态：第一次状态转移前，对于所有节点，选择自己时子树的快乐指数和为它自己的快乐指数，即：$dp[u][1] = happy[u]$。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int[] heads, happy, vals, nexts; // 邻接表存图
    static int n, idx;
    static boolean[] hasBoss;
    static int[][] dp;
    
    static void add(int a, int b) {
        vals[idx] = b;
        nexts[idx] = heads[a];
        heads[a] = idx++;
    }
    
    static void dfs(int u) {
        dp[u][1] = happy[u];
        for (int i = heads[u]; i != -1; i = nexts[i]) {
            int v = vals[i];
            dfs(v);
            dp[u][0] += Math.max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        heads = new int[n + 1];
        Arrays.fill(heads, -1);
        happy = new int[n + 1];
        vals = new int[n];
        nexts = new int[n];
        hasBoss = new boolean[n + 1];
        dp = new int[n + 1][2];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            happy[i] = (int) in.nval;
        }
        for (int i = 1; i < n; ++i) {
            in.nextToken();
            int k = (int) in.nval;
            in.nextToken();
            int l = (int) in.nval;
            add(l, k);
            hasBoss[k] = true;
        }
        int root = 1;
        while (hasBoss[root]) ++root; // 找根节点
        dfs(root);
        System.out.println(Math.max(dp[root][0], dp[root][1]));
    }
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 6010;
int heads[N], happy[N], vals[N], nexts[N];
int n, idx;
int dp[N][2];
bool has_boss[N];

void add(int a, int b) {
    vals[idx] = b;
    nexts[idx] = heads[a];
    heads[a] = idx++;
}

void dfs(int u) {
    dp[u][1] = happy[u];
    for (int i = heads[u]; ~i; i = nexts[i]) {
        int v = vals[i];
        dfs(v);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main() {
    memset(heads, -1, sizeof(heads));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &happy[i]);
    for (int i = 1; i < n; ++i) {
        int l, k;
        scanf("%d%d", &l, &k);
        add(k, l);
        has_boss[l] = true;
    }
    int root = 1;
    while (has_boss[root]) ++root;
    dfs(root);
    printf("%d\n", max(dp[root][0], dp[root][1]));
    
    return 0;
}