算法1

树形dp

这个题需要特判一下一个点都不选是最大值的情况，然后就是一个树形dp

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 100010, M = 2 * N, INF = 1e8;

LL f[N][2];

int h[N], e[M], ne[M], idx;

LL w[N];

int n;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int fa)
{
    f[u][1] = w[u];
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs(j, u);
        LL k = max(f[j][0], f[j][1]);
        if(f[j][1] > 0) f[u][1] += f[j][1];
        f[u][0] = max(f[u][0], k);
    }
}

int main()
{
    scanf("%d", &n);
    bool tag = true;
    LL maxv = -INF;
    for(int i = 1; i <= n; ++ i)
    {
        scanf("%lld", &w[i]);
        maxv = max(maxv, w[i]);
        if(w[i] > 0) tag = false;
    }
    if(tag)
    {
        printf("%d", maxv);
        return 0;
    }
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n - 1; ++ i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1, -1);
    printf("%lld", max(f[1][0], f[1][1]));
    return 0;
}

```