洛谷P1352 没有上司的舞会

树形dp水题

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 6010

using namespace std;

struct node
{
    int ed,nxt;
};
node edge[maxn<<1];
int n,m,first[maxn],cnt,dp[maxn][2];
int happy[maxn];

inline void add_edge(int s,int e)
{
    ++cnt;
    edge[cnt].ed=e;
    edge[cnt].nxt=first[s];
    first[s]=cnt;
    return;
}

inline void dfs(int now,int pre)
{
    for(register int i=first[now];i;i=edge[i].nxt)
    {
        int e=edge[i].ed;
        if(e!=pre)
        {
            dfs(e,now);
            dp[now][1]+=dp[e][0];
            dp[now][0]+=max(dp[e][0],dp[e][1]);
        }
    }
    dp[now][1]+=happy[now];
    return;
}

int main()
{
    scanf("%d",&n);
    for(register int i=1;i<=n;++i)
        scanf("%d",&happy[i]);
    for(register int i=1;i<=n-1;++i)
    {
        int s,e;
        scanf("%d%d",&s,&e);
        add_edge(s,e);
        add_edge(e,s);
    }
    dfs(1,0);
    printf("%d
",max(dp[1][1],dp[1][0]));
    return 0;
}