树形DP · 没有上司的舞会（动态演示+核心代码）

▶ 📖 问题描述 & 算法原理

没有上司的舞会：公司有 N 名职员，编号1~N，每位职员有一个快乐值 h[i]。职员之间存在上下级关系，构成一棵树（根为CEO）。现在要邀请一些职员参加舞会，但不能同时邀请一个职员和他的直接上司。求能获得的最大快乐值总和。

输入格式：
第一行：N
第二行：h[1] ... h[N]
接下来 N-1 行：u v（表示u是v的上司，或v是u的上司，按树边给出）
示例输入（5节点）：
5
5 3 4 2 6
1 2
1 3
2 4
3 5

📌 算法原理

状态定义： dp[u][0] 表示以 u 为根的子树中，不选 u 时的最大快乐值；
dp[u][1] 表示以 u 为根的子树中，选 u 时的最大快乐值。

转移方程：
dp[u][0] = sum( max(dp[v][0], dp[v][1]) ) （孩子可选可不选）
dp[u][1] = h[u] + sum( dp[v][0] ) （孩子一定不选）

其中 v 是 u 的所有子节点。

⚠️ 为什么用后序遍历？
因为孩子节点的dp值必须先于父节点计算，所以采用 DFS 后序遍历（从叶子到根）。

🌳 树形DP · 没有上司的舞会