【题目来源】
Acwing：285. 没有上司的舞会 - AcWing题库
【题目描述】
Ural 大学有 \(N\) 名职员，编号为 \(1\sim N\)。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 \(H_i\) 给出，其中 \(1\le i\le N\)。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
【输入】
第一行一个整数 \(N\)。
接下来 \(N\) 行，第 \(i\) 行表示 \(i\) 号职员的快乐指数 \(H_i\)。
接下来 \(N-1\) 行，每行输入一对整数 \(L,K\)，表示 \(K\) 是 \(L\) 的直接上司。（注意一下，后一个数是前一个数的父节点，不要搞反）。
【输出】
输出最大的快乐指数。
【输入样例】
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
【输出样例】
5
【算法标签】
《AcWing 285 没有上司的舞会》 #动态规划# #树形DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 6005; // 定义最大节点数
int n; // 节点数量
int w[N]; // 存储每个节点的权值
int f[N][5]; // f[u][0]表示不选节点u时的最大权值和，f[u][1]表示选节点u时的最大权值和
int h[N], e[N], ne[N], idx; // 邻接表存储树结构
bool st[N]; // 用于标记节点是否有父节点，帮助找到根节点// 添加一条从a到b的边
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}// 深度优先搜索，计算每个节点的f[u][0]和f[u][1]
void dfs(int u)
{f[u][1] = w[u]; // 选择当前节点u，初始化为u的权值for (int i = h[u]; i != -1; i = ne[i]) // 遍历u的所有子节点{int j = e[i]; // 子节点jdfs(j); // 递归处理子节点jf[u][0] += max(f[j][0], f[j][1]); // 不选u时，累加子节点j选或不选的最大值f[u][1] += f[j][0]; // 选u时，只能累加不选子节点j的值}
}int main()
{cin >> n; // 输入节点数量for (int i = 1; i <= n; i++) cin >> w[i]; // 输入每个节点的权值memset(h, -1, sizeof(h)); // 初始化邻接表头指针为-1for (int i = 0; i < n - 1; i++) // 输入n-1条边，构建树结构{int a, b; cin >> a >> b; // 输入边的两个节点add(b, a); // 添加从b到a的边，表示b是a的父节点st[a] = true; // 标记a有父节点} int root = 1;while (st[root]) root++; // 找到没有父节点的节点，即为根节点dfs(root); // 从根节点开始深度优先搜索cout << max(f[root][0], f[root][1]) << endl; // 输出根节点选或不选的最大权值和return 0;
}
【运行结果】
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
5