Aimee

很简单的树上dp

一维就够了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int x,y;
int zn[160001];
struct e{
    int to;
    int ne;
}ed[160001];
int p;
int dp[160001];
int head[160001];
void add(int f,int to){
    p++;
    ed[p].ne=head[f];
    ed[p].to=to;
    head[f]=p;
    return ;
}
void dfs(int now,int fa){
    for(int i=head[now];i;i=ed[i].ne){
        if(ed[i].to==fa)
        continue;
        dfs(ed[i].to,now);
    }
    for(int i=head[now];i;i=ed[i].ne){
        if(ed[i].to==fa)
        continue;
        dp[now]=max(dp[now],dp[now]+dp[ed[i].to]); 
    }
    if(dp[now]>0){
        dp[now]=max(0,dp[now]+zn[now]);
    }else{
        dp[now]=max(0,max(dp[now]+zn[now],zn[now]));
    }
    return ;
}
int ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&zn[i]);
    }
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(2,0);
    for(int i=1;i<=n;++i){
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}