http://lx.lanqiao.cn/problem.page?gpid=T14

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int dp[N][2];
vector<int> g[N];
int n,a,b;
void dfs(int u,int pre)//当前结点和前一个结点
{
    for(int i=0;i<g[u].size();i++)
    {
        int j = g[u][i];
        if(j!=pre)
        {
            dfs(j,u);
            dp[u][0]+=max(dp[j][0],dp[j][1]);
            dp[u][1]+=dp[j][0];
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>dp[i][1];// 选第i个点所得的权值
    }

    for(int i=1;i<=n-1;i++)
    {
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);//构建邻接表
    }
    dfs(1,0);// 从第一个结点开始搜索 
    cout<<max(dp[1][0],dp[1][1]);
    return 0;
}