The problem can be found here

My Thought Process

Ok, calculating the cost if we pick $1$ is pretty simple. We just need to keep track of the distances from $1$ to every other node and then multiply that distance by $a_i$. We can just use some basic DP to do that.

Now, how do we calculate the max cost though? Well what happen if we try to pick another neighboring node. Well, the distance to the nodes “behind” the previous node increase by one and the ones in front decrease by one.

Look at the first sample, if the first node picked is $1$ and then $4$ is picked, we decrease our current answer by $7$ and add $9, 4, 1, 10, 1, 6, 5$. We can do this in dfs order. We can keep track of the sum of the values in a subtree and then when we move to it, we substract the subtree and add the sum of $a_i$ minus that subtree (to get the nodes that increased).

Implementation

  1. dfs calculate the distances from $1$ and the sum of the subtrees
  2. find $total$, the starting answer if you pick $1$ as the node.
  3. dfs2, when you visit a new node, add the nodes with increase ddistance $a_i$ $(s[1] - s[u])$ and subtract $s[u]$, the subtree sum at that node because the distance from the picked node to the subtree nodes decreased by one.
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

#define int long long

const int MOD = 1e9+7;
const int MAXN = 2e5 + 5;
const int INF = 2e9;    
const long long IINF = 2e18;

vector<int> v(MAXN);
vector<vector<int>> g(MAXN);
vector<bool> vis(MAXN);
vector<int> d(MAXN, 2e9 + 5);
vector<int> s(MAXN, 0);
int total = 0;
int ans = 0;

void dfs(int x, int p){
    if(vis[x]){return;}
    vis[x] = true;

    for(int u : g[x]){
        if(vis[u] || u == p){
            continue;
        }
        d[u] = d[x] + 1;
        dfs(u, x);
        s[x] += s[u];
    }

    if(g[x].size() == 0){
        s[x] = v[x];
    }
}

void dfs2(int x, int p, int c){
    ans = max(ans, c);
    if(vis[x]){return;}
    vis[x] = true;

    for(int u : g[x]){
        if(vis[u] || u == p){
            continue;
        }
        dfs2(u, x, c + s[1] - 2 * s[u]);
    }
}

void solve() { 
    int n;
    cin >> n;

    for(int i = 1; i <= n; ++i){
        cin >> v[i];
        s[i] += v[i];
    }

    for(int i = 0; i < n - 1; ++i){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

    d[1] = 0;
    dfs(1, -1);

    int c = 0;
    for(int i = 1; i <= n; ++i){
        c += v[i] * d[i];
        vis[i] = false;
    }
    total = c;

    dfs2(1, -1, c);

    cout << ans << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    solve();

    return 0;
}

See here for the solution and another implementation.