【题解】没有上司的舞会

题目: 没有上司的舞会

题意:

Ural 大学有 N 名职员，编号为 1∼N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

第一行一个整数 N。

接下来 N 行，第 i 行表示 ii 号职员的快乐指数 Hi。

接下来N−1 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤6000,
−128≤Hi≤127

输入样例：

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例：

5

思路:

• 首先什么是树形dp？其实主要就是指存储方式是以树的形式存储，在优化时是在树的基础上进行优化的。
• 怎么去找到最优解？对于一个结点来说，以它为根节点的树的最大快乐值就是它的所有子树的最大值之和。分为两种情况，要么不含这个根节点，要么含有这个根节点。如果含有这个根节点，显然它的子树在计算最大值时，都不能含有与这个根节点直接相连的结点。如果不含这个根节点，那么它的子树既可以含有与这个根节点直接相连的，也可以不含有与这个根节点直接相连的结点，最后取最大值即可（在计算子树的最大值时，计算方式与根节点的计算方式相同）。
• 对于树的dfs，每个结点可以保证只遍历一次。

代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=6010;

int h[N*2],e[N*2],ne[N*2],idx;//这里其实没有必要乘2，不过一般来讲是个好习惯
int hp[N];
//f[i] [0]表示不选i结点的情况下以i为根节点的树的最大快乐值
//f[i] [1]是选择i结点的前提下以i为根节点的数的最大快乐值
int f[N][2];
int has_f[N];//记录是否有父节点，以此确定整棵树的根节点
int n;

void add(int a,int b)
{
    //本质上是插入一个头结点，h数组实际上是由许多链表的头结点组成
    e[idx]=a,ne[idx]=h[b],h[b]=idx++;
}

void dfs(int x)
{
    //树形dp的搜索通常要比图简单，因为不需要去考虑是否会反复搜索的问题，树的深搜遍历每个结点只会遍历一遍
    f[x][1]+=hp[x];
    
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        
        f[x][1]+=f[j][0];
        f[x][0]+=max(f[j][1],f[j][0]);
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>hp[i];
    
    memset(h,-1,sizeof h);
    
    for(int i=1;i<n;++i)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        has_f[a]=1;
    }
    
    int root=1;
    while(has_f[root])root++;
    
    dfs(root);
    cout<<max(f[root][0],f[root][1]);
    
    return 0;
    
}