题目描述

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

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

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

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

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

输入格式：

第一行一个整数N。
接下来N行，第 i 行表示 i 号职员的快乐指数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算法：

1）以所有人的关系建立一棵二叉树，u作为其中一棵二叉子树的根节点，代表某人的直接上司，其儿子节点用s[i]表示作为其直接下属，以此向下建立各自的二叉关系子树。

（2）结合题意建立动态规划转移方程，即集合为max(f[u][1],f[u][0])，其中状态划分为：f[u][2](0,1分别表示选与不选这个点的方案），集合表示的是所有以u为根的子树中选择，并且代表选（或不选）择这个点的所有方案。

（3）

以其中一棵二叉关系数为例分别讨论选与不选当前父节点的状态转移计算式：

（1）其中f（s1,0）,f(s2,0)表示父节点u的俩个儿子结点，所以求max f[u][0]就是不选父节点u的情况下，俩个儿子结点可以分为选此儿子结点，或者不选此儿子俩种情况来求其所有选择的方案数（使得欢乐指数最大），因此其状态计算式为：f[u][0]=max(f[s][1],f[s][0]).

(2)maxf[u][1]就是在选此节点u的情况下，其儿子结点就不能选（题目要求），那么使得其欢乐指数最大的方案数，就是不选儿子结点（所有以儿子结点作为父节点的二叉关系树的所有方案数），因此其状态计算式为：f[u][1]=maxf[s][0].

(3)结合俩种情况，归纳出其转态转移计算式为：f[u]=max(f[u][0],f[u][1]),其中f[u][1]=max(f[s][0],f[s][1]),f[u][0]=maxf[s][0].

时间复杂度分析：由于建立了二叉树，所以算法本质上是深度遍历搜索二叉树的每一个结点，因此其时间复杂为O（n).

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=6010;
int n;
int happy[N];//用来存储每个人的欢乐指数
int h[N],e[N],ne[N],idx;
//有向图的邻接表存储就是对于每个点 v 对应一个头节点, 记录在h[v]
//idx是图里边的编号，和建图的顺序有关，对于某一个点v, 它的所有邻边的编号不一定是连续的。
//e 数组是edge的缩写，记录了某一条有向边的终点
//ne数组是next的缩写，记录了邻接表里的同一个点的下一条邻边的idx
//ne[idx]=h[a]; h[a]=idx; 就是把新建的边插入队头。(先把新建的边的next指向现在队头的next，然后更新队头的next）
//然后再idx++, 给下一次建边使用
int f[N][2]; //开辟一个二维数组，用于存储每一个结点，且有0和1俩种状态
bool has_father[N]; //用来寻找根节点
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;//邻接表存储边
}
void dfs(int u)
{
    f[u][1]=happy[u]; //选择当结点时，存储当前结点的欢乐指数
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];   
          dfs(j);  //递归求解
          f[u][0]+=max(f[j][0],f[j][1]);
          f[u][1]+=f[j][0];
    }
}
int main()
{
    scanf("%d\n",&n);
    for(int i=1;i<=n;i++) scanf("%d",&happy[i]);
       memset(h,-1,sizeof h);
       for(int i=0;i<n-1;i++)
       {
           int a,b;
           scanf("%d%d",&a,&b);
           has_father[a]=true;
             add(b,a);
       }
       int root=1;  //用于寻找根结点，根结点即父节点为0的结点
       while(has_father[root]) root++;
       //用于判断当前结点是否有，有就继续遍历，没有就跳出循环
       dfs(root);
       printf("%d\n",max(f[root][0],f[root][1]));
       return 0;

}