没有上司的舞会

思路分析

这道题很难，但很简单。

经过两秒半的审题和思考，大家都能看出来职工们的关系为一棵以校长为根的树，同时，我们一看到使快乐指数最大这类的文字，就知道了这是一个典型的动规题目。又是树的，又是动规的，我寻思着，这不就是一道典型的树形动规题目吗？！

先科普一下树形动规。

（几年前，我刚看到这道题时，也知道是树形动规，但是就是不知道怎么做，后来一想，按当初我的水平，怎么可能做出来这种绿题呢？！）

废话少做，言归正传：

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。

——OI-Wiki

再看向这道题。

既然是动规题，那么就要构建一个动规数组。

仔细看，发现构建一个二维数组不太现实。因为我们的限制条件不是什么“nn 元钱”，也不是什么“nn 秒钟”，而是对于每一个职工，要么不让他参加舞会，要么不然他的直接上司参加舞会，或者两个都别参加也行，总之他们其中的一个不能参加舞会。所以我们是没有办法构建一个二维数组的，因为根本没有第一维的限制常量。考虑使用一维数组。

可以这样：

对于职工 ii，分两种情况：

  1. 不选，最大快乐值为 fif_i；
  2. 选，最大快乐值为 gig_i；

最后，程序结束前，输出 max⁡{fi,gi}\max\{f_i,g_i\} 即可。

等等，你还没说转移方程呢！

别急，慢慢来。

设职工ii的快乐值为ri.wr_i.w，存有所有直接下属编号的数组为ri.vr_i.v，即有：

  1. 不选，即对于他的每个直接下属，可以取他的选或不选中的快乐值最大的那个，但不能加上自己的快乐值（因为不选嘛），即为：fi=∑j=0∣ri.v∣−1max⁡{fri.vj,gri.vj}f_i=\sum_{j=0}^{|r_i.v|-1}\max\{f_{r_i.v_j},g_{r_i.v_j}\}；
  2. 选，即对于他的每个直接下属，都得选不选他的快乐值，但最后还要加上自己的快乐值（因为选嘛），即为：gi=(∑j=0∣ri.v∣−1fri.vj)+ri.wg_i=(\sum_{j=0}^{|r_i.v|-1}f_{r_i.v_j})+r_i.w

于是，代码便出来了。

交流电(AC)代码：

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
#include<iostream>
#include<vector>
#include<bitset>
using namespace std;
struct s
{
    int w{};
    vector<int>v;
}r[8192];
int n, o, f[8192], g[8192];
bitset<8192>b;
static void h(int x)
{
    for (int i{}; i < r[x].v.size(); i++)
        h(r[x].v[i]), f[x] += (f[r[x].v[i]] > g[r[x].v[i]] ? f[r[x].v[i]] : g[r[x].v[i]]), g[x] += f[r[x].v[i]];
}
int main()
{
    cin >> n;
    for (int i{ 1 }; i <= n; i++)
        cin >> r[i].w, g[i] = r[i].w;
    for (int i{ 1 }; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        r[y].v.push_back(x);
        b[x] = true;
    }
    for (int i{ 1 }; i <= n; i++)
        if (!b[i])
        {
            o = i;
            break;
        }
    h(o);
    cout << (f[o] > g[o] ? f[o] : g[o]);
    return 0;
}