题解 | #没有上司的舞会#

题目链接

没有上司的舞会

题目描述

公司要举办一场晚会，员工的上下级关系构成一棵树。规定如果邀请了某名员工，则不能邀请他的直接上司。每名员工参加晚会都能为晚会增添一份气氛值（可能为负数）。请求出晚会可能获得的最大气氛值总和。

输入:

第一行输入一个整数 $N$ ，表示员工数量。
第二行输入 $N$ 个整数，表示每名员工对应的气氛值 $w_i$ 。
接下来 $N-1$ 行，每行输入两个整数 $l, k$ ，表示 $l$ 是 $k$ 的直接上司。

输出:

输出一个整数，代表可获得的最大气氛值总和。

解题思路

这是一个典型的 树形动态规划 (Tree DP) 问题。我们需要对树上的每个节点做出决策（邀请或不邀请），并从子节点的决策中推出父节点的决策，最终得到根节点的全局最优解。

构建树与寻找根节点:
- 首先，根据输入的上下级关系，构建一个邻接表来表示这棵树。
- 同时，我们需要找到树的根节点，即那个没有上司的员工。我们可以用一个布尔数组记录哪些员工作为下属出现过，唯一没有作为下属出现过的员工就是根。
状态定义:
- 我们对每个节点 $u$ 定义两个状态：
  - $dp[u][0]$ : 在以 $u$ 为根的子树中，不邀请员工 $u$ 时，能获得的最大气氛值。
  - $dp[u][1]$ : 在以 $u$ 为根的子树中，邀请员工 $u$ 时，能获得的最大气氛值。
状态转移:
- 我们通过深度优先搜索（DFS），以后序遍历的方式来计算DP值。对于节点 $u$ 和它的所有直接下属 $v$ ：
  - 计算 $dp[u][0]$ (不邀请 $u$ ):
    - 如果我们不邀请 $u$ ，那么对于它的任何一个直接下属 $v$ ，我们既可以邀请也可以不邀请。为了使气氛值最大化，我们应该为每个下属 $v$ 选择更优的方案，即 $\max(dp[v][0], dp[v][1])$ 。
    - 因此， $dp[u][0] = \sum_{v \in \text{children}(u)} \max(dp[v][0], dp[v][1])$ 。
  - 计算 $dp[u][1]$ (邀请 $u$ ):
    - 如果我们邀请 $u$ ，首先我们会获得 $u$ 本身的气氛值 $w_u$ 。
    - 根据规则，我们不能邀请 $u$ 的任何直接下属 $v$ 。
    - 因此，对于每个下属 $v$ ，我们只能选择不邀请它的方案，即 $dp[v][0]$ 。
    - 因此， $dp[u][1] = w_u + \sum_{v \in \text{children}(u)} dp[v][0]$ 。
最终答案:
- 在DFS从根节点返回后，我们得到了根节点的两个DP值。全局的最大气氛值就是邀请根节点和不邀请根节点两种情况中的较优者，即 $\max(dp[\text{root}][0], dp[\text{root}][1])$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> w;
vector<vector<int>> adj;
vector<vector<long long>> dp;

void dfs(int u, int p) {
    // 初始状态：邀请u，获得u的价值
    dp[u][1] = w[u - 1];

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        // 状态转移
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

int main() {
    int N;
    cin >> N;
    w.resize(N);
    adj.resize(N + 1);
    dp.assign(N + 1, vector<long long>(2, 0));
    vector<bool> has_boss(N + 1, false);

    for (int i = 0; i < N; ++i) {
        cin >> w[i];
    }

    for (int i = 0; i < N - 1; ++i) {
        int l, k;
        cin >> l >> k;
        adj[l].push_back(k);
        adj[k].push_back(l); // 建无向边，用父节点参数避免向上走
        has_boss[k] = true;
    }

    int root = -1;
    for (int i = 1; i <= N; ++i) {
        if (!has_boss[i]) {
            root = i;
            break;
        }
    }

    dfs(root, -1);
    cout << max(dp[root][0], dp[root][1]) << "\n";

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int[] w;
    static List<List<Integer>> adj;
    static long[][] dp;

    public static void dfs(int u, int p) {
        // 初始状态
        dp[u][1] = w[u - 1];

        for (int v : adj.get(u)) {
            if (v == p) continue;
            dfs(v, u);
            // 状态转移
            dp[u][0] += Math.max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        w = new int[N];
        adj = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }
        dp = new long[N + 1][2];
        boolean[] hasBoss = new boolean[N + 1];

        for (int i = 0; i < N; i++) {
            w[i] = sc.nextInt();
        }

        for (int i = 0; i < N - 1; i++) {
            int l = sc.nextInt();
            int k = sc.nextInt();
            adj.get(l).add(k);
            adj.get(k).add(l); // Build undirected graph
            hasBoss[k] = true;
        }

        int root = -1;
        for (int i = 1; i <= N; i++) {
            if (!hasBoss[i]) {
                root = i;
                break;
            }
        }

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

import sys

# 增加递归深度限制
sys.setrecursionlimit(200000)

def dfs(u, p):
    # 初始状态：邀请u，获得u的价值
    dp[u][1] = w[u - 1]
    
    # 遍历子节点
    for v in adj[u]:
        if v == p:
            continue
        dfs(v, u)
        # 状态转移
        dp[u][0] += max(dp[v][0], dp[v][1])
        dp[u][1] += dp[v][0]

# 读取输入
N = int(input())
w = list(map(int, input().split()))

adj = [[] for _ in range(N + 1)]
has_boss = [False] * (N + 1)

# 注意题目输入可能不只N-1行，循环直到读完
try:
    while True:
        l, k = map(int, input().split())
        adj[l].append(k)
        adj[k].append(l) # 建无向边
        has_boss[k] = True
except EOFError:
    pass

# 寻找根节点
root = -1
for i in range(1, N + 1):
    if not has_boss[i]:
        root = i
        break

# dp[u][0] -> 不邀请u, dp[u][1] -> 邀请u
dp = [[0] * 2 for _ in range(N + 1)]
dfs(root, -1)
print(max(dp[root][0], dp[root][1]))

算法及复杂度

算法：树形动态规划
时间复杂度： $O(N)$ - 我们需要对整棵树进行一次深度优先搜索，每个节点和每条边都只访问常数次。
空间复杂度： $O(N)$ - 主要开销来自存储树的邻接表、DP数组以及DFS的递归栈深度。