目录

• 题目描述
• 前言
• C++代码

题目描述

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

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

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

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

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

输入格式
第一行一个整数 NNN。

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

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

输出格式
输出最大的快乐指数。

数据范围
1≤N≤6000,1≤N≤6000,1≤N≤6000,
−128≤Hi≤127−128≤H_i≤127−128≤Hi​≤127

输入样例：

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

输出样例：

5

前言

首先，如果将“上司”看作父结点，“下属”看作子结点，那么按照样例的员工从属关系，可以得到如下的一棵树。

而样例输出的 “5”，就是如图所示的五个蓝色结点组合而来，因为此时5号不是1、2、6、7的直接上属，可以将他们安排在同一个舞会，所以最大快乐指数就是它们的快乐指数之和。

如何考虑用树形DP的方法来做呢？

可以看到对于树中的每个结点，它都对应有两个选择：去或是不去舞会，即选不选中该结点。

• 如果选中该结点，那么它的所有直接子结点（如果有）都不可以被选择，因为如果此时还选择子结点也不会得到子结点的快乐指数。
• 如果没有选中该结点，那么它的所有子结点选不选择都可以。

于是，可以找到DP的状态表示，即：

f(u,0/1)f(u,0/1)f(u,0/1)：
集合：表示以uuu为根结点（注意这不一定指总树的根），其所有子树的快乐指数和；
属性：最大值。
其中f(u,0)f(u,0)f(u,0)表示方案中不包含uuu结点，而f(u,1)f(u,1)f(u,1)则表示方案中包含。

那么状态转移：
如果以happy[u]表示u结点的快乐指数，那么一开始，至少f[u][1] = happy[u]，因为这表示选择了自己当最高层领导（相对于子结点讲），那就起码会有自己的快乐指数。

然后就是上面两项选择的转义，即

• 如果选择结点u，那就只能加上直接下属不能被选择的方案，假设子结点为j（会有很多个），则f(u,1)=Σ(f(j,0))f(u,1) = Σ(f(j,0))f(u,1)=Σ(f(j,0))。
• 如果不选择结点u，由于直接下属可被选择也可不被选择，所以取一个max，即f(u,0)=Σ(max[f(j,0),f(j,1)])f(u,0) = Σ(max[f(j,0), f(j,1)])f(u,0)=Σ(max[f(j,0),f(j,1)])。

有了两个转移方程，那就只需从根结点开始往下，深搜一遍对于每个结点状态更新一遍。

最后的答案就在f(总根结点，0)f(总根结点，0)f(总根结点，0)和f(总根结点，1)f(总根结点，1)f(总根结点，1)两个方案里取一个max。

C++代码

#include 
#include 
#include 
using namespace std;const int N = 6010;int f[N][2];        //f[u][*]：表示以u为根，其所有子树快乐指数和的最大值；0表示不选择u参加，1表示选择了u参加的方案。
int e[N], ne[N], h[N], idx = 0;
int happy[N];       //u的快乐指数
bool has_father[N];     //为了找根结点
int 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);//状态转移方程，对每一个jf[u][0] += max(f[j][0], f[j][1]);f[u][1] += f[j][0];}
}int main(){memset(h, -1, sizeof h);cin >> n;for(int i = 1;i <= n;i ++)      cin >> happy[i];for(int i = 1;i <= n - 1;i ++){int a, b;cin >> a >> b;add(b, a);      //b是a的父结点所以要b——>a才能成树has_father[a] = true;}int root = 1;while(has_father[root])     root ++;dfs(root);cout << max(f[root][0], f[root][1]) << endl;return 0;
}