洛谷P1352 没有上司的舞会

题目描述

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

输入输出格式

输入格式：

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

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

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

最后一行输入0 0

输出格式：

输出最大的快乐指数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

/*
    这是一道简单的树形DP，也算是入了一个门（坑）了。
    dp[i][j]表示的是员工j的状态为i时的最大快乐度
    状态i分为0和1，分别表示他不去和去
    然后分类讨论：如果员工j不去，那么他的下属可去可不去
    所以就有dp[0][j] = Sum(max(dp[0][son(j)],dp[1][son(j)]))
    如果员工j去 那么他的下属就只能不去了233333
    那么dp[1][j] = Sum(dp[0][son(j)])
    如果员工j去，那么最后还要加上他的快乐值r[j]
    然后找到根节点dfs 算出的就是所有的快乐值的最大值
    于是这题就做完了
*/

#include <bits/stdc++.h>

using namespace std;

const int maxn = 6010;

int head[maxn],fa[maxn],r[maxn];
int n,cnt,dp[2][maxn];

struct node{
    int to,pre;
}G[maxn];

void addedge(int from,int to){
    G[++cnt].to = to;
    G[cnt].pre = head[from];
    head[from] = cnt;
}

void dfs(int u){
    for(int i = head[u];i;i = G[i].pre){
        int v = G[i].to;
        dfs(v);
        dp[0][u] += max(dp[0][v],dp[1][v]);//u不去 
        dp[1][u] += dp[0][v];//u去 
    }
    dp[1][u] += r[u];
}

int main(){
    int x,y,root;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) scanf("%d",&r[i]);
    for(int i = 1;i <= n-1;i++){
        scanf("%d%d",&y,&x);
        addedge(x,y);fa[y] = x;
    }
    for(int i = 1;i <= n;i++){
        if(fa[i] == 0){
            root = i;
            break;
        }
    }
    dfs(root);
    printf("%d",max(dp[1][root],dp[0][root]));
    return 0;
}