树形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;
}

全部评论

相关推荐

06-04 09:27
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务