题目描述

精简解法：

C++ 代码

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

int main()
{
    int n;
    cin>>n;
    vector<vector<int>>mp(n+1);
    vector dp(n+1,vector<int>(2));
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    function<void(int, int)>dfs= [&](int u, int fa) {
        dp[u][1] = a[u];
        for (auto i : mp[u]) {
            if (i == fa)continue;
            dfs(i, u);
            dp[u][0] += max(dp[i][1], dp[i][0]);
            dp[u][1] += dp[i][0];
        }
        };
    dfs(1, 0);
    cout<<max(dp[1][0],dp[1][1]);
}