Kvar_ispw17's blog
0%

Posted on In

题目链接： Luogu 1352 没有上司的舞会

题目大意

有一个舞会，里面的人有上司的关系，每个人有一个快乐值 \(w[i]\)，如果一个人的直接上司也来了，则这个人就再也不愿意来跳舞了。（快乐值有正有负）

题解

题目给了一个树形关系，我们设 \(\text{dp}[i][j]\) 表示第 \(i\) 的人去或不去（\(j=0\) 不去，\(j=1\) 去）时，以其为根的子树所能达到的最大快乐值的和。注意到最终答案便是 \(\text{max}\{\text{dp}[root][0],\text{dp}[root][1]\}\).

如何进行 $ $ 转移？我们根据题目给的关系：

  1. 若 \(i\) 来则：\(\text{dp}[i][1]=w[i]+\displaystyle\sum_{c=\text{ch}[i]}\text{dp}[c][0]\)
  2. 若 \(i\) 不来则：\(\text{dp}[i][0]=\displaystyle\sum_{c=\text{ch}[i]}\text{max}\{\text{dp}[c][0],\text{dp}[c][1]\}\)

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 6e3 + 5;

template <typename _Tp>
void read(_Tp &a, char c = 0) {
    for(c = getchar(); !isdigit(c); c = getchar());
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}

ll n, root, a[N], fa[N], dp[N][2];
vector<ll> ch[N];

void dfs(int p) {
    //printf("at %d\n", p);
    if(ch[p].empty()) {
        dp[p][1] = a[p];
        return;
    }
    vector<ll>::iterator it = ch[p].begin();
    ll cnt = 0;
    for(; it != ch[p].end(); it++) {
        int c = *it;
        dfs(c);
        dp[p][1] += dp[c][0];
        cnt += max(dp[c][0], dp[c][1]);
    }
    dp[p][1] += a[p];
    dp[p][0] = cnt;
}

int main() {
    // freopen("t2.in", "r", stdin);
    read(n);
    int c, f;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < n; i++) {
        read(c), read(f);
        ch[f].push_back(c);
        fa[c] = f;
    }
    for(int i = 1; i <= n; i++) {
        if(!fa[i]) {
            root = i;
            //cout << root << endl;
        }
    }
    dfs(root);
    cout << max(dp[root][0], dp[root][1]) << endl;
    return 0;
}