[Luogu-P1352] 没有上司的舞会

发表于 | 更新于 | 分类于 ， ，
本文字数： 12k

链接

\(\text{Luogu-P1352 没有上司的舞会}\)

题意

  \(\text{Ural}\)大学有\(N\)名职员，编号\(1\dots N\)，它们的关系是一棵以校长为根的树，父节点即是子结点的直接上司。每个职员有一个快乐指数\(H_i\)。现在这里有一场宴会，但是没有职员愿意和直接上司一起参会，在此条件下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，输出这个最大值。

  数据范围：\(1\le N \le 6000,-128\le H_i\le 127\).

分析

  在树上设计动态规划算法时，一般以结点从深到浅（子树从小到大）的顺序作为\(\text{DP}\)的阶段，\(\text{DP}\)的状态表示时，第一维通常为结点编号（表示以该节点为根的子树），而第二维为从子树中选出的满足某种条件的结点的个数，第三维为选择或者不选择当前结点（所以它有\(0\)和\(1\)两种取值），有时第二维或者第三维可以省略。大多时候采用递归形式实现树形动态规划（所以\(dfs\)这时很好用），对于每个结点，先递归在它的每个子节点上\(dp\)，回溯时，从子结点向结点x进行状态转移。

  对于本题来说，以使用\(dp[i][0]\)表示从以\(i\)为根中的子树中选择一部分结点，并且\(i\)不选，\(dp[i][1]\)表示选\(i\)；

  如果结点\(x\)不选，那么它的子节点可以选也可以不选，则有 \[dp[x][0]=\displaystyle \sum_{y\in Son(x)}\max\{dp[y][0],dp[y][1]\}\]

  \(Son(x)\)表示\(x\)的子节点集合，如果\(x\)选，那么它的子节点一定不能选，则有： \[dp[x][1]=H_x+\displaystyle \sum_{y\in Son(x)}dp[y][0]\]

  此题我们还需要找出这棵树的根。另外，树形\(dp\)是一种很优美的动态规划。

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
    //char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar(); int x = 0, f = 1;
        while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
        while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}

using namespace fastIO;
using namespace std;

int n, r[6009], vis[6009], f[6009][2];
vector<int>vec[6009];

void dfs(int u) {
    f[u][1] = r[u];
    f[u][0] = 0;
    for (int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        dfs(v);
        f[u][1] += f[v][0];
        f[u][0] += max(f[v][1], f[v][0]);
    }
}


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> r[i];
    int a, b;
    for (int i = 1; i <= n - 1; i++) {
        cin >> a >> b;
        vis[a] = 1;
        vec[b].push_back(a);
    }
    int root;
    for(int i = 1; i <= n; i++)
        if (!vis[i]) {
            root = i;
            break;
        }
    dfs(root);
    cout << max(f[root][0], f[root][1]) << endl;
}

```