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

这是一个经典的树形动态规划问题，通常被称为“没有上司的舞会”或“树的最大权独立集”问题。

核心思想

由于公司的人员结构是一棵树，且限制条件是“直接上司和下属不能同时出席”，这意味着在树中，如果选择了某个节点，就不能选择它的父节点和子节点。我们需要在满足这个条件的前提下，选择一个节点集合，使得权值（气氛值）之和最大。

这是一个典型的在树上做决策的问题。对于树中的每一个节点（员工），我们只有两种选择：

邀请该员工。
不邀请该员工。

当前节点的决策会影响其子节点的决策范围，因此我们可以使用动态规划，从叶子节点向根节点（自底向上）递推计算最优解。

状态定义： 设 $u$ 为当前节点（员工），我们需要维护两个状态：

$dp[u][0]$ ：表示不邀请员工 $u$ 时，以 $u$ 为根的子树能获得的最大气氛值。
$dp[u][1]$ ：表示邀请员工 $u$ 时，以 $u$ 为根的子树能获得的最大气氛值。

状态转移方程： 假设 $v$ 是 $u$ 的直接下属（子节点）：

如果邀请 $u$ ( $dp[u][1]$ )： 根据规则， $u$ 的直接下属 $v$ 绝不能被邀请。因此， $u$ 被邀请时的最大值 = $u$ 自身的气氛值 + 所有子节点 $v$ 不被邀请时的最大值之和。 $dp[u][1] = w_u + \sum_{v \in children(u)} dp[v][0]$
如果不邀请 $u$ ( $dp[u][0]$ )： 既然 $u$ 不出席，那么 $u$ 的直接下属 $v$ 可以出席，也可以不出席。为了利益最大化，对于每个子节点 $v$ ，我们应该在“邀请 $v$ ”和“不邀请 $v$ ”两种情况中选择较大的那个。因此， $u$ 不被邀请时的最大值 = 0 + 所有子节点 $v$ 的最优解之和。 $dp[u][0] = \sum_{v \in children(u)} \max(dp[v][0], dp[v][1])$

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
 ios::sync_with_stdio(false);
 cin.tie(nullptr);

 int n;
 cin >> n;
 vector<int> w(n + 1);
 for (int i = 1; i <= n; i++)
     cin >> w[i];
 vector<vector<int>> graph(n + 1);
 vector<bool> hasBoss(n + 1, false);
 for (int i = 1; i < n; i++) {
     int k, l;
     cin >> k >> l;
     graph[k].push_back(l);
     hasBoss[l] = true;
 }

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

 vector<vector<int>> dp(n + 1, vector<int>(2));
 auto dfs = [&](auto&& dfs, int u)->void {
     dp[u][0] = 0;
     dp[u][1] = w[u];

     for (int v : graph[u]) {
         dfs(dfs, v);
         dp[u][1] += dp[v][0];
         dp[u][0] += max(dp[v][0], dp[v][1]);
     }
 };
 dfs(dfs, root);

 int ans = max(dp[root][0], dp[root][1]);
 cout << ans << endl;
}

复杂度分析

时间复杂度： $O(n)$
- 构建邻接表需要遍历所有边，时间为 $O(n)$ 。
- DFS 遍历过程中，每个节点仅被访问一次，每条边也仅被处理一次。
- 状态转移的计算量与节点的度数成正比，总计算量与边数成正比，即 $O(n)$ 。
- 因此，总时间复杂度为线性。
空间复杂度： $O(n)$
- 需要邻接表来存储树结构，空间为 $O(n)$ 。
- 需要 $dp$ 数组存储每个节点的状态，大小为 $2 \times n$ ，即 $O(n)$ 。
- DFS 递归调用栈的深度在最坏情况下（链状树）为 $O(n)$ 。
- 因此，总空间复杂度为 $O(n)$ 。