P8625 [蓝桥杯 2015 省 B] 生命之树

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
vector<int> Edge[N];
int n, arr[N], dp[N][2], x, y;
void dfs(int x, int fa) {
    for (int i : Edge[x])
        if (i != fa)
            dfs(i, x);
    dp[x][0] = INT_MIN; // 不选自己
    for (int i : Edge[x])
        if (i != fa)
            dp[x][0] = max(dp[x][0], max(dp[i][0], dp[i][1]));
    // 选自己
    dp[x][1] = arr[x];
    for (int i : Edge[x])
        if (i != fa)
            dp[x][1] += max(0LL, dp[i][1]);
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    for (int i = 1; i < n; i++) {
        cin >> x >> y;
        Edge[x].push_back(y);
        Edge[y].push_back(x);
    }
    dfs(1, 0);
    cout << max(0LL, max(dp[1][0], dp[1][1]));
}