[题解] P1352 没有上司的舞会

¶凉笙 · 2021-02-03 21:30:23 · 个人记录

树上DP

传送门

题意描述（做题即翻译）

有n个员工要参加舞会，每个人对应一个权值a[ i ]，某人参加舞会当且仅当他的上司没有参加舞会，求舞会的最大权值和

DP分析:

1.状态选择：

由于要考虑某个人参不参加舞会对他指向的点的影响，因此必须有一维来记录他参不参加舞会，明显地，由于是树上dp，还有一维就是以当前这个人为根的子树最大权值和。

因此本题的状态找到了：这是DP的最重要的工作。

2.状态转移：

首先考虑对于某个结点u，显然 u 会对它指向的所有v都产生影响，分为两种情况，因此舞会的权值和也会受影响，采用回溯时的逆推思路

2.1. f[ u ][ 0 ]:u 如果不选，v可选可不选，取最大值即可

f[u][0]+=max(f[v][0],f[v][1]);

2.2. f[ u ][ 1 ]:u 选了，v 一定不选

f[u][1]+=f[v][0]

3.考虑初始化：

f[ u ][ 1 ] = a[ u ],f[ u ][ 0 ] = 0。

因此

#include <iostream>
#include <algorithm>
#include <cstdio>
#define re register
using namespace std;
const int maxn=6005;
int head[maxn],cnt=0,n,f[maxn][2],a[maxn],ans=0,vis[maxn];
struct tree{
    int to,nxt;
}e[maxn];
inline void link(int u,int v){
    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
inline void solve(int u){
    f[u][1]=a[u];f[u][0]=0;
    for(re int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        solve(v);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
    }
}
int main(){
    scanf("%d",&n);
    for(re int i=1;i<=n;i++)scanf("%d",a+i);
    for(re int i=1;i<=n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        link(v,u);
        vis[u]=true;
    }
    int root;
    for(re int i=1;i<=n;i++)if(!vis[i]){root=i;break;}
    solve(root);
    cout<<max(f[root][1],f[root][0]);
    return 0;
}