题目描述
某大学有 n 个职员，编号为 1…n。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入格式
输入的第一行是一个整数 n。
第 2 到第(n 1) 行，每行一个整数，第 (i 1) 行的整数表示 i 号职员的快乐指数 r_i。
第 (n 2) 到第 2n 行，每行输入一对整数 l,k，代表 k 是 l 的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
输入输出样例
输入 #1
代码语言：javascript复制7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
输出 #1
代码语言：javascript复制5
说明/提示
数据规模与约定
对于 100% 的数据，保证 ，，，且给出的关系一定是一棵树。
题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P1352
- 参考题解：https://www.luogu.com.cn/problem/solution/P1352
- 标签：
OI、动态规划、树形DP
正解
- 树形dp，设为以i为根的子树能得到的最大快乐指数，同时i不参加舞会，代表i参加时的最大快乐指数
- 上司参加舞会，则下属可以参加也可以不参加，那么转移方程：
- 上司参加舞会下属一个都不会参加，此时转移方程：
- 通过dfs求解答案，同时我们不用建立额外的数组a，可以将的值直接存在里
代码
代码语言：javascript复制#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
struct node {
int v, next;
} g[6005];
int head[6005], cnt = 0, dp[6005][2], is[6005], vis[6005];
void add(int u, int v) {
g[ cnt].v = v;
g[cnt].next = head[u];
head[u] = cnt;
}
void dfs(int k) {
vis[k] = 1;
for (int i = head[k]; i; i = g[i].next) {
if (vis[g[i].v]) {
continue;
}
dfs(g[i].v);
dp[k][1] = dp[g[i].v][0];
dp[k][0] = max(dp[g[i].v][0], dp[g[i].v][1]);
}
return;
}
void best_coder() {
int n;
cin >> n;
for (int i = 1; i <= n; i) {
cin >> dp[i][1];
}
for (int i = 1; i < n; i) {
int l, k;
cin >> l >> k;
is[l] = 1;
add(k, l);
}
for (int i = 1; i <= n; i){
if (!is[i]) {
dfs(i);
cout << max(dp[i][1], dp[i][0]);
}
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
