AcWing 285. 没有上司的舞会
原题链接
简单
作者:
B1ackGod
,
2021-02-09 23:41:40
,
所有人可见
,
阅读 357
核心:动态规划,树形dp,可以利用dfs完成状态转移
- 状态表示:f[u][1]表示以u为根节点的所有子树和包含u这个节点的快乐值总和。
f[u][0]表示以u为根节点的所有子树和不包含这个节点的快乐值总和。
- 属性:max
- 状态计算:
①选了u,那么他的直接子节点就一定不能选。 f[u][1]=f[son1][0]+f[son2][0]…
②不选u,那么他的直接子节点可选或可不选,取决于哪种方案的快乐值最大。
f[u][1]=max(f[son1][0],f[son1][1])+max(f[son2][0],f[son2][1])…
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=6010;
int f[N][2];
int h[N],e[N],ne[N],idx;
int happy[N];
int father[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
//利用dfs完成状态转移
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(){
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin>>happy[i];
memset(h, -1, sizeof h);
for(int i=1; i<n; i++){
int a, b;
cin>>a>>b;
add(b,a);//父节点指向子节点
father[a]=b;
}
//查找根节点
int root=0;
for(int i=1; i<=n; i++){
if(father[i]==0)
root=i;
}
dfs(root);
printf("%d",max(f[root][1],f[root][0]));
return 0;
}