没有上司的晚会（树形DP）

解题思路:树形DP

问题转化：将 "选择不相邻节点以获得最大价值" 的问题，转化为每个节点的两种状态决策

    选当前节点：则不能选任何子节点

    不选当前节点：子节点可选可不选（取最优）

动态规划状态设计：

    dp[p][1]：选择节点p时，以p为根的子树能获得的最大价值

    dp[p][0]：不选择节点p时，以p为根的子树能获得的最大价值

状态转移方程：

    选择节点p：价值 = 节点p自身价值 + 所有子节点不被选择的价值总和

    不选择节点p：价值 = 所有子节点 "选或不选的最大值" 的总和

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;

// 定义常量和全局变量
const int N = 1e4 + 10;  // 节点最大数量（10000+10，防止越界）
int n;                   // 实际节点数量
int v[N];                // 存储每个节点的价值
int nop[N];              // 标记节点是否有父节点（1表示有父节点，0表示无父节点）
// dp[p][0]表示不选择节点p时的最大价值
// dp[p][1]表示选择节点p时的最大价值
int dp[N][2];            
vector <int> tree[N];    // 邻接表存储树结构（tree[p]存储p的所有子节点）

// 深度优先搜索，计算每个节点的dp值
void dfs(int p){
    // 初始化dp值：
    // 不选当前节点，初始价值为0
    dp[p][0] = 0;
    // 选择当前节点，初始价值为当前节点自身的价值
    dp[p][1] = v[p];
    
    // 遍历当前节点的所有子节点
    for(int i = 0; i < tree[p].size(); ++ i){
        int c = tree[p][i];  // c为当前节点的子节点
        dfs(c);              // 递归处理子节点
        
        // 状态转移：
        // 不选当前节点时，子节点可选可不选，取最大值累加
        dp[p][0] += max(dp[c][0], dp[c][1]);
        // 选当前节点时，子节点一定不能选，只能累加不选子节点的情况
        dp[p][1] += dp[c][0];
    }
}

int main()
{
    cin >> n;  // 输入节点数量
    
    // 输入每个节点的价值（节点编号从1开始）
    for(int i = 0; i < n; ++ i)    
        cin >> v[i + 1];
    
    // 输入树的边（x是y的子节点），直到输入0 0结束
    int x, y;
    while(cin >> x >> y && x != 0){
        nop[x] = 1;               // 标记x有父节点
        tree[y].push_back(x);     // 将x加入y的子节点列表
    }
    
    // 寻找根节点（没有父节点的节点）
    int root;
    for(int i = 1; i <= n; ++ i)
        if(!nop[i]) 
            root = i;
    
    // 从根节点开始DFS计算dp值
    dfs(root);
    
    // 最终结果是根节点选或不选的最大值
    cout << max(dp[root][0], dp[root][1]);
    return 0;
}