题解 | 没有上司的舞会

#include <bits/stdc++.h>
using namespace std;
int dp[200002][2]; // dp[n][0]表示第n个人没来的时候的值，1为来了的时候的值
int n;
vector<int> a(200002);
vector<int> e[200002]; // 存储所有与n相连的点
void dfs(int u, int fa)
{
    dp[u][0] = 0, dp[u][1] = a[u];
    for (int v : e[u])
    {
        if (v != fa) // 因为e[u]也包含着他的上司，避免dfs死循环
        {
            dfs(v, u);
            dp[u][0] += max(dp[v][0], dp[v][1]); // 如果上司不来的话，只能从他的下属的来与不来中选择一种值最大的情况
            dp[u][1] += dp[v][0];// 如果上司来的话，下属必须不来，只能是选择dp[v][0]
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i]; // 输入每一个节点对应的值
    }
    for (int i = 1; i < n; i++)
    {
        int k, l;
        cin >> k >> l;
        e[l].push_back(k), e[k].push_back(l); // 构建每一个所有的连接的数
    }
    dfs(1, 0);// 从根开始遍历
    cout << max(dp[1][0], dp[1][1]); // 选择是最高boss来的话大还是不来的大
    return 0;// 完结撒花：）
}

设dp_i,0 为i号点所在的子树内最大的权值和，且u为v的上司，v为u的下属

其实我感觉代码的注释写的挺清楚的了（）