没有上司的舞会

分析

分析一下题意，即在一棵树中找到一些子节点（其中任意两个节点没有边相连）使得这些节点的快乐值总和最大

dp分析

1. 状态表示$f[i][2]$ :

   • 集合：

     • $f[i][0]$：表示从以$i$为根节点的子树中选择节点（不包括根节点）
     • $f[i][1]$：表示从以$i$为根节点的子树中选择节点（包括根节点）

   • 属性：

     使得快乐值最大

2. 状态计算：

   对于每个子节点$s$，当父节点被选时不能不选，当父节点未选时既可以被选也可以不选，从中找到该子树的最大值

   • $f[i][1] += max(f[s][0])$
   • $f[i][0] += max(f[s][1],f[s][0])$

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 6010;
int happy[N];
int f[N][2];
int h[N], e[N], ne[N], idx;
bool has_father[N];
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int n;

void dfs(int r){
    
    f[r][1] = happy[r];
    for (int i = h[r]; i != -1; i = ne[i] ){
        int j = e[i];
        
        dfs(j);
        f[r][1] += f[j][0];
        f[r][0] += max(f[j][1],f[j][0]);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> happy[i];
    for (int i = 0; i < n - 1; i ++ ){
        int a,b;
        cin >> a >> b;
        has_father[a] = true;
        add(b, a);
    }
    
    int root = 1;
    while(has_father[root]){
        root++;
    }  
    dfs(root);
   cout << max(f[root][0],f[root][1]);
    return 0;
}

Q.E.D.