没有上司的舞会 题解

不懂树形dp的先看这里，已经会了的大神直接略过。。。
最大独立子集
最大独立子集的定义是，对于一个树形结构，所有的孩子和他们的父亲存在排斥，也就是如果选取了某个节点，那么会导致不能选取这个节点的所有孩子节点。
有向图和无向图是大同小异的，介于本题是有向图，直接简单的叙述有向图的最大独立子集。
首先，全局数组dp[N][2]
dp是一个二维数组，第一维度表示有多少个点，第二维度中，0表示不取，1表示取。
无非就是以下两种情况：

• 1.对于以root为根的子树，root这个点的值需要取，那么这个点的所有儿子是不能取的，答案为val[root]+ dp[son][0]
• 2.对于以root为根的子树，root这个点的值不需要取，那么这个点的所有儿子可以取也可以不取（所以选择最大的作为最优方案），答案为 max(dp[son][0],dp[son][1])

本题的几个注意点：
1.happy指数可能为负，答案有可能存在负数，maxhappy请初始化为负无穷
2.叶子结点本身的happy值有可能就是最大值，别忘了叶子节点也要对答案进行更新，否则你会只通过90%的样例（别问我怎么知道的。。。）
3.注意求和的方式，均使用“+=”

看懂了以上内容，再结合代码查看就非常简单啦，以下是代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int happy[6050];//快乐指数
bool havepar[6050];//表示有没有上司
bool haveson[6050];//表示有没有下属
vector <int> G[6050];
int dp[6050][2];
int maxhappy=-0x3f3f3f3f;
void dfs(int root)
{
    if(!haveson[root])//叶子
    {
        dp[root][1]=happy[root];
        dp[root][0]=0;
        maxhappy=max(maxhappy,max(dp[root][1],dp[root][0]));
        return;
    }
    for(int i=0;i<G[root].size();i++)
    {
        int to=G[root][i];
        dfs(to);
        dp[root][1]+=dp[to][0];
        dp[root][0]+=max(dp[to][1],dp[to][0]);
    }
    dp[root][1]+=happy[root];
    maxhappy=max(maxhappy,max(dp[root][1],dp[root][0]));
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&happy[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        havepar[u]=true;
        haveson[v]=true;
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!havepar[i])
        {
            dfs(i);
            break;
        }
    }
    printf("%d\n",maxhappy);
}