【POJ 2342】Anniversary party（入门树形dp）

饶文津

发布于 2020-06-02 15:45:53

3090

发布于 2020-06-02 15:45:53

文章被收录于专栏：饶文津的专栏饶文津的专栏

dp[i][0..1]表示i不来/来参加的最大总高兴值。

则dp[i][1]+=dp[v][0]（v是i的所有直接下属）

dp[i][0]+=max(dp[v][0],dp[v][1])

没有告诉你树根，dp的方向我第一次写的是用队列维护叶子节点，每次计算完，它的父亲的孩子数量--，如果减到0，就变成叶子加入队列。直到队列空。后来看别人写的两种是读入的时候维护root，还有种方法是记录父亲，然后递推祖先。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 6050
using namespace std;
int n,u,v,a[N],rt;
int dp[N][2],head[N],cnt;
struct edge{
    int to,next;
}e[N];
int DP(int u,int s){
    int &ans=dp[u][s];
    if(ans)return ans;
    if(s)ans=a[u];
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(s)ans+=DP(v,0);
        else ans+=max(DP(v,1),DP(v,0));
    }
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    while(scanf("%d%d",&v,&u),u){
        e[++cnt]=(edge){v,head[u]};
        head[u]=cnt;
        if(v==rt||!rt)rt=u;
    }
    if(!rt)rt=1;//如果只有一个节点的情况
    printf("%d",max(DP(rt,1),DP(rt,0)));
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-08-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除