题目描述
Ural 大学有 N 名职员,编号为 1∼N,他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数 Hi给出,其中 1≤i≤N。现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。
在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。
样例
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
算法
记忆化暴搜
枚举每个人,对存在上司或下属的人进行查找根节点,然后通过递归计算出这个根节点下的最大快乐值,并记录,对所有该树上节点标记,后续遍历到时不再查找。既不存在上司也不存在下属的人直接判断快乐值是否大于0,加到最终答案中即可。
在计算一棵树上的最大快乐值时,考虑选取根节点或根节点的直接子节点两种情况,选取根节点就递归遍历根节点的每个孙子树的最大快乐值。不选根节点就递归遍历每个子树的最大快乐值。最后相比较取最大快乐值加到最终答案中。
注意:这里求得的快乐值小于0的树,可以不选它所有的节点
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=6010;
int n,H[N],e[N],pa[N],res,ne[N],idx,h[N],tt[N];
bool st[N];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int tree(int u){
st[u]=1;
if(tt[u]!=-1)return tt[u];
int res1=0,res2=0;
if(H[u]>0)res1+=H[u];
for(int i=h[u];i!=-1;i=ne[i]){
int y=e[i];
res2+=tree(y);
for(int j=h[y];j!=-1;j=ne[j]){
int z=e[j];
res1+=tree(z);
}
}
tt[u]=res1>res2?res1:res2;
return tt[u];
}
void fun(int x){
int t=x;
while(pa[t])t=pa[t];
res+=tree(t);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(h,-1,sizeof h);
memset(tt,-1,sizeof tt);
cin>>n;
for(int i=1;i<=n;++i)cin>>H[i];
for(int i=1;i<=n-1;++i){
int L,K;
cin>>L>>K;
add(K,L);
pa[L]=K;
}
for(int i=1;i<=n;++i){
if(!pa[i]&&(h[i]==-1)&&H[i]>0)res+=H[i];
if(!st[i]&&(pa[i]||h[i]>=0))fun(i);
}
cout<<res<<endl;
return 0;
}