没有上司的舞会|P1352

https://www.luogu.com.cn/problem/P1352

题目描述

某大学有 个职员，编号为 1…n。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 ri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 n。

第 222 到第 (n+1) 行，每行一个整数，第 (i+1) 行的整数表示 iii 号职员的快乐指数 ri​。

第 (n+2) 到第 2n 行，每行输入一对整数 l,k，代表 k 是 l 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

输入输出样例

输入 #1

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出 #1

5

说明/提示

数据规模与约定

对于 100% 的数据，保证 1≤n≤6000，−128≤ri≤127，1≤l,k≤n，且给出的关系一定是一棵树。

树上DP入门

这道题我都觉得不难

//你就不可能觉得难

写一个hin简单的式子

dp[i]=max(dp[son[i]],dp[son[son[i]]]+r[i]);

这个转移就是，要么不来了，要么直接下属不来了，自己就可以来了，转移下下属的情况（下下属也可以不来，这里的dp[i]表示考虑了dp[i]及i的子树的最大值）

当然，这个方程不能直接转移，因为son有多个，就算预处理出来也是O(TLE)

但是我们发现一个事情，搜儿子的儿子时其实在儿子搜儿子时已经搜过了

那么当时我们可以直接把和就记下来

于是拿出dp[MAXN][2]

dp[i][0]//还是自己本身

dp[i][1]//帮自己父亲找他孙子用的

那很好转移啊

dp[i][0]=max(dp[son[i]][0],dp[son[i]][1]+r[i]);//简洁明了，因为就没变

dp[i][1]=dp[son[i]][0]//帮自己爹预处理一下

son数组不用真正处理，因为dfs满足了无后效性，后序遍历。

#include<iostream>
#include<cstring>
using namespace std;
//不会DP的蒟蒻
const int MAXN=6e3+10;
int r[MAXN];
int n;
//单向存边！
//链式前向星
struct tree{
    int to;
    int next;
}edge[MAXN];
int _cnt=0;
int head[MAXN];
void add(int u,int v){
    edge[++_cnt].to=v;
    edge[_cnt].next=head[u];
    head[u]=_cnt;
}
//练习打快读！
inline int read(){
    int s=0,f=1;
    char c=getchar();
    while(c<48 || c>57){if(c=='-')f=-f;c=getchar();}
    while(c>=48 && c<=57)s=s*10+c-48,c=getchar();
    return s*f;
}
//展现DP功底的时候到了
int dp[MAXN][2];
void dfs(int x){//这代码够短吧
    int total0=0;
    int total1=0;
    for(int i=head[x];i!=0;i=edge[i].next){
        int nxt=edge[i].to;
        dfs(nxt);
        total0+=dp[nxt][1];
        total1+=dp[nxt][0];
    }
    dp[x][0]=max(total0+r[x],total1);
    dp[x][1]=total1;
    return ;
}
bool rt[MAXN];
signed main(){
    n=read();
    int u,v;
    for(int i=1;i<=n;i++)r[i]=read();
    for(int i=1;i<n;i++){
        u=read(),v=read();
        add(v,u);
        rt[u]=1;//找根倒是得找
    }
    int root=0;
    for(int i=1;i<=n;i++){
        if(!rt[i]){
            root=i;
            break;
        }
    }
    dfs(root);
    cout<<dp[root][0];        
    return 0;
}