洛谷——P1122 最大子树和

P1122 最大子树和

树形DP，$f[u]$表示以u为根的子树的最大美丽指数

$f[u]+=max(0,f[v])$

树形DP的基本结构，先搜再DP，这题感觉有点儿贪心的性质，选就要选美丽值>0的子树

#include<bits/stdc++.h>

#define N 101010
using namespace std;


struct node{
    int to,next;
}e[N];
int n,head[N],tot,a[N],dp[N],ans;

void add(int u,int v){
    e[++tot].to=v,e[tot].next=head[u],head[u]=tot;
}

void dfs(int u,int f){
    dp[u]=a[u];
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v!=f){
            dfs(v,u);
            dp[u]+=dp[v]>0?dp[v]:0;
        }
    }
    ans=max(ans,dp[u]);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int u,v,i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    printf("%d
",ans);
    return 0;
}