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

在X森林里，上帝创建了生命之树。

他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。

上帝要在这棵树内选出一个非空节点集 S，使得对于 S 中的任意两个点 a,b，都存在一个点列 {a,v1,v2,…,vk,b} 使得这个点列中的每个点都是 S 里面的元素，且序列中相邻两个点间有一条边相连。

在这个前提下，上帝要使得 S 中的点所对应的整数的和尽量大。

这个最大的和就是上帝给生命之树的评分。

经过 atm 的努力，他已经知道了上帝给每棵树上每个节点上的整数。

但是由于 atm 不擅长计算，他不知道怎样有效的求评分。

他需要你为他写一个程序来计算一棵树的分数。

输入格式

第二行 n 个整数，依次表示每个节点的评分。

接下来 n−1 行，每行 2 个整数 u,v，表示存在一条 u 到 v 的边。

由于这是一棵树，所以是不存在环的。

树的节点编号从 1 到 n。

输出格式

数据范围

输入样例：

51 -2 -3 4 54 23 11 22 5

输出样例：

8

这道题与求最长连续子序列一样，求的是能构建成的树里面和谐值的和最大。

我们就求每个子节点的和谐值的和，如果得到的和谐值为负，我们就不去选它，然后和谐值大于0的我们就去加上这个点，因为这是树状图，所以我们要用到递归去实现一个树状dp 的计算，这应该是树状dp的最基础的题目了，我太菜了，一切题目一定要从先理解题目开始。

#include
   
    #include
    
     #include
     
      using namespace std;const int N=1e5+10;int wi[N];int f[N];int e[N*2],ne[N*2],h[N],idx;bool st[N];long long  ans=-0x3f3f3f3f;void add(int a,int b){       e[idx]=b;ne[idx]=h[a];h[a]=idx++;}long long dfs(int x){       st[x]=true;    long long res=wi[x];    for(int i=h[x];~i;i=ne[i])    {           int j=e[i];        if(!st[j])        {               int t=dfs(j);            if(t>0)            res+=t;        }    }    ans=max(ans,res);    return res;}int main(void){       memset(h,-1,sizeof h);    int n;    cin>>n;    for(int i=1;i<=n;i++) cin>>wi[i];    for(int i=1;i
      
       >a>>b;        add(a,b);        add(b,a);    }    dfs(1);    cout<
       
        <