本文共 726 字，大约阅读时间需要 2 分钟。

题意：给你n个节点，每个节点都有一个权值，还给你一些边，现在让你找一个非空子集，是的这个非空子集的和最大。

思路：使用树形dp，每个节点都有选和不选，在决定选还是不选的时候，把当前所有子树权值之和和0进行比较，如果是大于0，就选，如果是小于0就不选，这个题有一个坑点，题目要求是非空子集，有这样一种情况，所有的权值都是小于0的，这是也是必须要选一个的。

比赛的时候题意理解可能有点问题，把题意理解成不能n个节点全选了，郝老师说，前面那句话可能就是随口一提，只需要关注非空子集这一个条件即可。

#include 
   
    using namespace std;const int maxn=16010;vector
    
      v[maxn];int dp[maxn];const int ind=0x3f3f3f;int a[maxn];int n;int  dfs(int x,int fa){    dp[x]=a[x];    for(int i=0; i
     
      >n;    int ans=-10000;    for(int i=1; i<=n; i++)    {        cin>>a[i];    }    for(int i=0; i
      
       >x>>y;        v[x].push_back(y);        v[y].push_back(x);    }    dfs(1,-1);    for(int i=1; i<=n; i++)    {        ans=max(ans,dp[i]);    }    cout<
       
        <
       
      
     
    
   

转载地址：http://qfgsi.baihongyu.com/