【题目来源】
洛谷：P1352 没有上司的舞会 - 洛谷
【题目描述】
某大学有 \(n\) 个职员，编号为 \(1…n\)。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\)，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
【输入】
输入的第一行是一个整数 \(n\)。
第 \(2\) 到第 \((n+1)\) 行，每行一个整数，第 \((i+1)\) 行的整数表示 \(i\) 号职员的快乐指数 \(r_i\)。
第 \((n+2)\) 到第 \(2n\) 行，每行输入一对整数 \(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
【算法标签】
《洛谷 P1352 没有上司的舞会》 #动态规划DP# #树形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