没有上司的舞会 - 树形DP

---

题目描述

Ural 大学有 $N$ 名职员，编号为 $1\sim N$。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 $H_i$ 给出，其中 $1\le i\le N$。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式
第一行一个整数 $N$。

接下来 $N$ 行，第 $i$ 行表示 i 号职员的快乐指数 Hi。

接下来 $N-1$ 行，每行输入一对整数 $L,K$，表示 $K$ 是 $L$ 的直接上司。

输出格式
输出最大的快乐指数。

数据范围
$1\le N\le 6000,$
$-128\le H_i\le 127$

输入样例：

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出样例：

5
1

---

前言

首先，如果将“上司”看作父结点，“下属”看作子结点，那么按照样例的员工从属关系，可以得到如下的一棵树。

而样例输出的 “5”，就是如图所示的五个蓝色结点组合而来，因为此时5号不是1、2、6、7的直接上属，可以将他们安排在同一个舞会，所以最大快乐指数就是它们的快乐指数之和。

如何考虑用树形DP的方法来做呢？

可以看到对于树中的每个结点，它都对应有两个选择：去或是不去舞会，即选不选中该结点。

• 如果选中该结点，那么它的所有直接子结点（如果有）都不可以被选择，因为如果此时还选择子结点也不会得到子结点的快乐指数。
• 如果没有选中该结点，那么它的所有子结点选不选择都可以。

于是，可以找到DP的状态表示，即：

$f(u,0/1)$：
集合：表示以$u$为根结点（注意这不一定指总树的根），其所有子树的快乐指数和；
属性：最大值。
其中$f(u,0)$表示方案中不包含$u$结点，而$f(u,1)$则表示方案中包含。

那么状态转移：
如果以happy[u]表示u结点的快乐指数，那么一开始，至少f[u][1] = happy[u]，因为这表示选择了自己当最高层领导（相对于子结点讲），那就起码会有自己的快乐指数。

然后就是上面两项选择的转义，即

• 如果选择结点u，那就只能加上直接下属不能被选择的方案，假设子结点为j（会有很多个），则$f(u,1)=\Sigma (f(j,0))$。
• 如果不选择结点u，由于直接下属可被选择也可不被选择，所以取一个max，即$f(u,0)=\Sigma (max[f(j,0),f(j,1)])$。

有了两个转移方程，那就只需从根结点开始往下，深搜一遍对于每个结点状态更新一遍。

最后的答案就在$f(总根结点，0)$和$f(总根结点，1)$两个方案里取一个max。

---

C++代码

#include 
#include 
#include 
using namespace std;

const int N = 6010;

int f[N][2];        //f[u][*]：表示以u为根，其所有子树快乐指数和的最大值；0表示不选择u参加，1表示选择了u参加的方案。
int e[N], ne[N], h[N], idx = 0;
int happy[N];       //u的快乐指数
bool has_father[N];     //为了找根结点
int n;

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u){
    f[u][1] = happy[u];     //选择了自己，至少有自己的快乐指数。
    
    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];
        dfs(j);
        
        //状态转移方程，对每一个j
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 1;i <= n;i ++)      cin >> happy[i];
    for(int i = 1;i <= n - 1;i ++){
        int a, b;
        cin >> a >> b;
        add(b, a);      //b是a的父结点所以要b——>a才能成树
        has_father[a] = true;
    }
    
    int root = 1;
    while(has_father[root])     root ++;
    dfs(root);
    
    cout << max(f[root][0], f[root][1]) << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49