$$\color{Red}{没有上司的舞会-三种语言详细步骤解释}$$
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
Ural 大学有 N 名职员，编号为 1∼N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
输入格式
第一行一个整数 N。
接下来 N 行，第 i 行表示 i 号职员的快乐指数 Hi。
接下来 N−1 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。（注意一下，后一个数是前一个数的父节点，不要搞反）。
输出格式
输出最大的快乐指数。
数据范围
1 ≤ N ≤ 6000
−128 ≤ Hi ≤ 127
输入样例：
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
输出样例：
5
树形DP：dfs结合dp
我的战略游戏题解 类似的一道题目，也是状态机相关的树形dp
1.算法细节
- 不难看出，此题和树的重心 类似，只是存值使用了两个维度的状态表达式，但是为什么树的重心我们采用了st的bool数组，代表一个点是否可以遍历到，本题却不用了呢？
非常简单，树的重心是无向图，我们在求一颗确定根节点的树的结点数量，利用了这些边去遍历结点，我们使用st的bool数组是为了防止遍历过程中走到根节点之上，陷入死循环。
本题是有向图，故不会出现遍历到根节点的可能。
- 如何设计状态表达式和状态方程？为什么计算各不相同？
本体的领导关系以一颗树的图来保存，一个人来与不来的幸福最大值是不同的，会影响到直系下属来与不来，所以这里不能以一维的动态规划来计算，不妨设置为二维分别表示来与不来。
f[i][j（0 -> 不来 / 1 -> 来）]:代表着i号职员不来或来的最大幸福指数。
状态方程计算各不相同。
这里是状态机的思想，但是职员之间的关系使用的是树来存储和线性不同
f[root][1] = max(f[son 1][0] + f[son 2][0] + '''' + f[son n][0])
f[root][0] = max(max(f[son 1][0], f[son 1][1]) + max(f[son 2][0], f[son 2][1]) + '''' + max(f[son n][0], f[son n][1]))
一个人来幸福指数的最大值应该是他的直系下属均不来的方案下的幸福指数。而一个人不来，幸福指数的最大值既可能是他的直系下属来的情况，也可能是直系下属不来的情况，因此需要取最大值加入这个方案中。
2.具体代码
java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 6010, idx, n;
static int[] happy = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] h = new int[N];
static boolean[] st = new boolean[N];
static int[][] f = new int[N][N];
static void add(int x, int y) {
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
static void dfs(int x){
f[x][1] = happy[x];
f[x][0] = 0;
for (int i = h[x]; i != -1; i=ne[i]) {
int son = e[i];
dfs(son);
f[x][1] += f[son][0];
f[x][0] += Math.max(f[son][1], f[son][0]);
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
Arrays.fill(h, -1);
n = Integer.parseInt(br.readLine());
for (int i = 1; i <= n; i++) happy[i] = Integer.parseInt(br.readLine());
for (int i = 0; i < n - 1; i++) {
String[] s1 = br.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
add(b, a);
st[a] = true;
}
int root = 1;
while(st[root]) root ++;
dfs(root);
System.out.println(Math.max(f[root][1], f[root][0]));
}
}
python3
import sys
sys.setrecursionlimit(1000000)
N = 6010
happy = [0] * N
has_father = [0] * N
e = [0] * N
h = [-1] * N
ne = [0] * N
idx = 0
f = [[0] * 2 for i in range(N)]
def dfs(x):
f[x][1] = happy[x]
i = h[x]
while i != -1:
j = e[i]
dfs(j)
f[x][1] += f[j][0]
f[x][0] += max(f[j][1], f[j][0])
i = ne[i]
def add(a, b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
if __name__ == '__main__':
n = int(input())
for i in range(1, n+1): happy[i] = int(input())
for i in range(n-1):
a, b = map(int, input().split())
add(b, a)
has_father[a] = True
# 找寻boss节点
root = 1
while has_father[root]: root += 1
dfs(root)
res = max(f[root][1], f[root][0])
print(res)
C++
#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
int n, happy[N], f[N][2];
int e[N], ne[N], h[N], idx;
bool has_father[N];//通过它找到真正的根结点
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int x)
{
f[x][1] = happy[x];
for(int i=h[x]; i!=-1; i=ne[i])
{
int y = e[i];
dfs(y);
f[x][1] += f[y][0];
f[x][0] += max(f[y][1], f[y][0]);
}
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++) scanf("%d", &happy[i]);
memset(h, -1, sizeof h);
int a, b;
for(int i=1; i<n; i++)
{
cin >> a >> b;
add(b, a);
has_father[a] = true;
}
int root = 1;
while(has_father[root]) root ++;
dfs(root);
printf("%d", max(f[root][1], f[root][0]));
return 0;
}
