树形dp之最大独立集(模板)
题目: 没有上司的舞会
最大独立集:一条边的两点至多选一个点,即父亲和儿子不能同时选
f[i][0]表示不选i点时的以i为根的子树最大快乐指数
f[i][1]表示选i点时的以i为根的子树最大快乐指数
f[i][0]= ( max(f[j][1],f[j][0]) )
f[i][1]=f[j][0]+hi[i]
j是i的儿子
边界:f[i][0]=0,f[i][1]=hi————i是叶子结点
ans=max(f[root][0],f[root][1]);
include<bits/stdc++.h>
using namespace std;
int const N=6e3+7;
int n,cnt;
int head[N];
struct node{
int a,next,len;
}edge[N<<1];
void add(int x,int y,int len){
edge[++cnt].a =y;
edge[cnt].len =len;
edge[cnt].next =head[x];
head[x]=cnt;
}
int hi[N],f[N][2],tot[N],vis[N],ans;
void dfs(int x){ f[x][1]=hi[x];f[x][0]=0; vis[x]=1; for(int i=head[x];i;i=edge[i].next){ if(vis[edge[i].a]) continue; vis[edge[i].a]=1; dfs(edge[i].a); f[x][0]+=max(f[edge[i].a][0],f[edge[i].a][1]); f[x][1]+=f[edge[i].a][0]; } ans=max(f[x][0],f[x][1]); }
int main(){
cin >> n;
for(int i=1;i<=n;++i){
cin >> hi[i];
}
int a,b;
for(int i=1;i<=n-1;++i){
cin >> a >> b;
add(a,b,1);add(b,a,1);
}
cin >> a >> b;
dfs(1);
cout << ans;
return 0;
}