首个题解与较为专业的分析

这是一道标准的树形动态规划题目，我们能从题目得到以下信息：

1. 各个子节点的权值（废话）
2. 本题的数据结构——树（核心）

简化一下：假如本题只有三个节点：总经理(23)——员工A(10)、B(15)，那么有两种方案：

1. 邀请父节点，不要子节点，得到的权值为23
2. 邀请两个子节点，得到权值25

但是这个时候问题又来了，我们能直接丢一个max上去吗？不行。你可以试试
所以本体的核心是一个二维数组dp，一边表示该节点“参加”这一状态，另一边相反。
使用 DFS（深度搜索）算法由叶节点最优值向上更新至父节点的最优值。
更新（状态）值存储在二维状态（dp）数组中。

dfs核心代码

void dfs(int x){
    dp[x][0]=0,dp[x][1]=r[x];
    for(int i=0; i<ve[x].size(); i++){
        int y=ve[x][i];
        dfs(y);
        dp[x][0]+=max(dp[y][1],dp[y][0]);
        dp[x][1]+=dp[y][0];
    }
}

完整代码

#include<iostream>
#include<vector>
using namespace std;
int n,r[6005],dp[6005][2];
vector<int> ve[6005];
bool vis[6005];
void dfs(int x){
    dp[x][0]=0,dp[x][1]=r[x];
    for(int i=0; i<ve[x].size(); i++){
        int y=ve[x][i];
        dfs(y);
        dp[x][0]+=max(dp[y][1],dp[y][0]);
        dp[x][1]+=dp[y][0];
    }
}
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){cin>>r[i];}
    for(int i=1; i<n; i++){
        int u,v; cin>>u>>v;
        ve[v].push_back(u);
        vis[u]=1;
    }
    int id=-1;
    for(int i=1; i<=n; i++){
        if(vis[i]==0){
            id=i;
        }
    }
    dfs(id);
    cout<<max(dp[id][0],dp[id][1]);
    return 0;
}

如果你觉得有帮助，点个赞吧