题目描述

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

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

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

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

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

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

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

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

输入格式

第一行一个整数 $n$ 表示这棵树有 $n$ 个节点。

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

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

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

树的节点编号从 $1$ 到 $n$。

输出格式

输出一行一个数，表示上帝给这棵树的分数。

数据范围

$1 \le n \le 10^5$,
每个节点的评分的绝对值均不超过 $10^6$。

输入样例：

5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

输出样例：

8

算法

(暴力枚举) $O(n^2)$

write here…

时间复杂度

write here…

空间复杂度

write here…

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=2*N;
typedef long long ll;
ll f[N];
int w[N],h[N],e[M],ne[M],eidx;
void add(int u,int v){
    e[eidx]=v;
    ne[eidx]=h[u];
    h[u]=eidx++;
}
void dfs(int u,int father){
    f[u]=w[u];
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j!=father){
            dfs(j,u);
            f[u]+=max(0ll,f[j]);
        }
    }
}
int main(){
    int n;
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&w[i]);
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
   dfs(1,-1);
   ll res=f[1];//保守一点
   for(int i=1;i<=n;i++)res=max(res,f[i]);
   cout<<res;

}