树形DP

状态划分

集合:f[u]再以u为根的子树中包含u的所有连通块的权值的最大值

直接爆搜f[u] = W[u] + 所有连边的其他连通块的最大值,即统计一下就ok

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define N 100010
#define M N*2
using namespace std;

typedef long long LL;

int n;
int w[N];
int h[N],e[M],ne[M],idx;
LL f[N];

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

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()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);

    for(int i = 1;i <= n;i ++)  scanf("%d",&w[i]);
    for(int i = 0;i < n - 1;i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }

    dfs(1,-1);

    LL res = f[1];
    for(int i = 2;i <= n;i ++)  res = max(res,f[i]);

    printf("%lld\n",res);

    return 0;
}