把DP搬到树上。

题目描述

某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数$R_i$，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入输出格式

输入格式

第一行一个整数N。(1<=N<=6000)

接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

最后一行输入0 0

输出格式

输出最大的快乐指数。

INPUT & OUTPUT’s examples

Input’s e.g. #1

Output’s e.g. #1

分析

比较经典的树形dp题目。

由题意知，树上的节点只有两种情况，即选或不选（有些像背包啊）。

那么分情况讨论吧：

对于当前节点，如果选择，则与这个点相连的点都不能选。
如果不选，那么对于这个节点的子节点，就可以进行判断。

那么对于这两种情况取最优即可。

设$dp_{i,0}$表示，以$i$为根节点的子树，不选所得的最大价值。

而相对的，$dp_{i,1}$表示，以$i$为根节点的子树，选所得的最大价值。

所以列出状态转移方程：

$$dp_{i,0} = \sum max(dp_{j,0},dp_{j,1})$$（$j$是$i$的子节点）

$$dp_{i,1} = \sum dp_{tree[i].to,0}$$

最后直接输出$max(dp_{1,1},dp_{1,0})$即可。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cmath>
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
const int MAXN = 6e3+3;
struct Edge{
    int next,to;
};
Edge tree[MAXN<<1];
int dp[MAXN][2];
int arr[MAXN],n,head[MAXN],cnt;
/* functions */
inline void Add_Edge(int from,int to){
    tree[++cnt].next=head[from];
    tree[cnt].to=to;
    head[from]=cnt;
}
inline void DFS(int now,int father){
    dp[now][1]=arr[now];
    dp[now][0]=0;
    for(int i=head[now];i;i=tree[i].next){
        int u=tree[i].to;
        if(u==father)continue;
        DFS(u,now);
        dp[now][1]+=dp[u][0];
        dp[now][0]+=std::max(dp[u][1],dp[u][0]);
    }
}
inline void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
}
int main(int argc,char *argv[]){
    init();
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        Add_Edge(x,y);
        Add_Edge(y,x);
    }
    int x,y;
    scanf("%d%d",&x,&y);
    DFS(1,0);
    int ans=std::max(dp[1][0],dp[1][1]);
    printf("%d\n",ans);
    return 0;
}

洛谷P1352题解