解题报告 P1352 没有上司的舞会

题目内容

P1352

大意：某大学职员的从属关系是一棵树，有一场舞会，每人都有特定的快乐指数 r_i，但如果一个职员的直接上司参加了舞会，那么他一定就不会来了，求最大快乐指数和。

解题思路

经典的树形 dp，一般树形的 dp 都是每个子树每个子树一层层递归上去，现在考虑设计状态和状态转移：

设 f_{i,k} 表示以 i 号职员为树根的子树在 i 号职员去（ k=1 ）或不去（ k=0 ）的情况下能达到的最大快乐指数。

这样的正确性是显然的，由于所有员工的关系是树形，所以当一个子树的最优状态计算出来后，子树中的员工来或者不来就关系不大了，这个 dp 的无后效性体现在这里，最优子结构也可以体现：子树下面的子树达到最优了，显然整棵子树也是最优的。

方程式如下，x 一定为 i 的直属员工：

f_{i,0}=\sum\max(f_{x,0},f_{x,1})

如果这个员工 i 不去的话，总的快乐指数就是下面的所有员工去或不去能达到的最大快乐指数之和。

否则如果这个员工要去的话，那下面的直接员工都不会去，就是

f_{i,1}=\sum f_{x,0}+r_i

具体的实现就是 dfs 一层一层递归下去就可以了，当然不要忘记一开始确定树根的位置

#include <cstdio>
#include <vector>
#include <cctype>
using namespace std;

const int maxn=6e3+5;
vector<int> tree[maxn];
int r[maxn],n,fa[maxn],f[maxn][2];

inline int read()
{
    bool w=0;
    int x=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            w=1;
        c=getchar();
    }
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
    return w?-x:x;
}

void dfs(int s)
{
    for(auto i:tree[s])//遍历子树
    {
        dfs(i);
        f[s][0]+=max(f[i][0],f[i][1]);
        f[s][1]+=f[i][0];
    }
    f[s][1]+=r[s];
    return;
}

int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        r[i]=read();
    int l,k;
    for(int i=1;i<n;i++)
    {
        l=read(),k=read();
        tree[k].push_back(l);
        fa[l]++;//记录入度
    }
    int s;
    for(int i=1;i<=n;i++)
        if(!fa[i])//入度为0的节点就是根
        {
            s=i;
            break;
        }
    dfs(s);
    printf("%d\n",max(f[s][0],f[s][1]));
    return 0;
}