gJcvem - Online IDE & Debugging Tool

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

#define int long long

const int N = 200005;
int n;
int w[N], sub[N], dp[N];
vector<int> adj[N];
int res = 0;

void dfs_sub(int u, int p) {
    sub[u] = w[u];
    for (int v : adj[u]) if (v != p) {
        dfs_sub(v, u);
        sub[u] += sub[v];
    }
}

void dfs_dp(int u, int p) {
    dp[u] = sub[u];
    int best1 = 0, best2 = 0; // top 2 child contributions
    for (int v : adj[u]) if (v != p) {
        dfs_dp(v, u);
        dp[u] = max(dp[u], sub[u] + dp[v]);
        int val = dp[v];
        if (val > best1) {
            best2 = best1;
            best1 = val;
        } else if (val > best2) {
            best2 = val;
        }
    }
    res = max(res, sub[u] + best1 + best2);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs_sub(1, 0);
    dfs_dp(1, 0);

    cout << res << "\n";
    return 0;
}