Christmas Tree

#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
using pii = pair<int, int>;
template <typename T>
using Prior = std::priority_queue<T>;
template <typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define ef push_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

#ifdef local
#define debug(...) \
    cerr << "\u001b[33m" << "LINE " << __LINE__ << ": (" << #__VA_ARGS__ << ") = ",\
    _do(__VA_ARGS__),\
    cerr << "\u001b[0m"
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", "; _do(_u...);}
#define fastIO()
#else
#define debug(...) void()
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#endif

template <typename T> bool chmin(T &lhs, T rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T> bool chmax(T &lhs, T rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

const int lgmx = 18 + 5;
const int maxn = 2E5 + 5;

int N;
vector<int> adj[maxn], dep(maxn, 0);
vector<vector<int>> anc(lgmx, vector<int>(maxn, 0));

vector<int> c_ch[maxn], c_fa(maxn), c_sz(maxn, 0), c_val(maxn, 0), c_val_fa(maxn, 0), c_vis(maxn, 0);
vector<vector<int>> c_dis(lgmx, vector<int>(maxn, 0));
vector<int> tmp_sz(maxn), tmp_max_adj(maxn);

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int lay = lgmx-1; lay >= 0; --lay) {
        if ((dep[x] - dep[y]) >> lay) x = anc[lay][x];
    }
    if (x == y) return x;
    for (int lay = lgmx-1; lay >= 0; --lay) {
        if (anc[lay][x] != anc[lay][y]) x = anc[lay][x], y = anc[lay][y];
    }
    return anc[0][x];
}

int get_dist(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

int find_centroid(int now, int tot_sz, int par = 0) {
    tmp_sz[now] = 1, tmp_max_adj[now] = 0;
    int cent = 0;
    for (int x : adj[now]) {
        if (c_vis[x] or x == par) continue;
        chmax(cent, find_centroid(x, tot_sz, now));
        tmp_sz[now] += tmp_sz[x], chmax(tmp_max_adj[now], tmp_sz[x]);
    }
    chmax(tmp_max_adj[now], tot_sz - tmp_sz[now]);
    if (2 * tmp_max_adj[now] <= tot_sz) chmax(cent, now);
    return cent;
}

void add_value(int id) {
    for (int now = id, lay = 0; now; now = c_fa[now], ++lay) {
        ++c_sz[now], c_val[now] += c_dis[lay][id];
        if (c_fa[now]) c_val_fa[now] += c_dis[lay+1][id];
    }
}

int calc_cost(int id) {
    int ans = c_val[id];
    for (int now = id, lay = 0; c_fa[now]; now = c_fa[now], ++lay) {
        ans += c_val[c_fa[now]] - c_val_fa[now] + (c_sz[c_fa[now]] - c_sz[now]) * c_dis[lay+1][id];
    }
    return ans;
}

int move_centroid(int L, int R) {
    int M = lca(L, R), ans = M, min_cost = calc_cost(M);
    while (L != M) {
        if (chmin(min_cost, calc_cost(L))) ans = L;
        L = anc[0][L];
    }
    while (R != M) {
        if (chmin(min_cost, calc_cost(R))) ans = R;
        R = anc[0][R];
    }
    return ans;
    /*
    int M = lca(L, R), milo, mihi;
    int len_l, len_r, cost_l, cost_r;
    while (L != M and R != M) {
        // debug("step1"s, L, M, R);
        len_l = dep[L] - dep[M], len_r = dep[R] - dep[M];
        milo = anc[__lg(len_l-1)][L], mihi = anc[__lg(len_r-1)][R];
        cost_l = calc_cost(milo), cost_r = calc_cost(mihi);
        if (cost_l < cost_r) R = anc[0][mihi];
        else                 L = anc[0][milo];
    }
    if (L == M) swap(L, R);
    R = M;
    while (dep[L] - dep[R] > 1) {
        // debug("step2"s, L, R);
        len_l = dep[L] - dep[R];
        milo = anc[__lg(len_l-1)][L], mihi = anc[0][milo];
        cost_l = calc_cost(milo), cost_r = calc_cost(mihi);
        if (cost_l < cost_r) R = milo;
        else                 L = mihi;
    }
    return calc_cost(L) <= calc_cost(R) ? L : R;
    */
}

void dfs_init(int now, int par = 0) {
    dep[now] = dep[par] + 1, anc[0][now] = par;
    for (int x : adj[now]) {
        if (x == par) continue;
        dfs_init(x, now);
    }
}

void lca_build() {
    for (int lay = 1; lay < lgmx; ++lay) {
        for (int i = 1; i <= N; ++i) anc[lay][i] = anc[lay-1][anc[lay-1][i]];
    }
}

int centroid_build(int now, int siz) {
    int cent = find_centroid(now, siz);
    c_vis[cent] = 1;
    // debug(now, siz, cent);
    for (int x : adj[cent]) {
        if (c_vis[x]) continue;
        int ch_cent = centroid_build(x, siz - tmp_max_adj[x]);
        c_ch[cent].eb(ch_cent), c_fa[ch_cent] = cent;
    }
    return cent;
}

void centroid_dis_build() {
    for (int i = 1; i <= N; ++i) {
        for (int now = c_fa[i], lay = 1; now; now = c_fa[now], ++lay) {
            c_dis[lay][i] = get_dist(i, now);
        }
    }
}

void solve() {
    cin >> N;

    vector<int> H(N), id(N);
    for (int &x : H) cin >> x;
    H.insert(begin(H), 0);
    iota(ALL(id), 1);
    sort(ALL(id), [&](int &x, int &y) {return H[x] < H[y];});

    for (int i = 0, u, v; i < N-1; ++i) {
        cin >> u >> v;
        adj[u].eb(v), adj[v].eb(u);
    }
    dfs_init(1), lca_build();
    int c_root = centroid_build(1, N);
    centroid_dis_build();

    // debug(c_root);
    // for (int i = 1; i <= N; ++i) debug(i, dep[i], anc[0][i], c_fa[i], c_vis[i]);
    // for (int lay = 0; lay < 3; ++lay) {
        // for (int i = 1; i <= N; ++i) debug(lay, i, c_dis[lay][i]);
    // }

    int ans = 0, cost, cent = c_root, root;
    for (int i : id) {
        add_value(i);
        // for (int j = 1; j <= N; ++j) debug(j, c_sz[j], c_val[j], c_val_fa[j]);
        root = move_centroid(cent, i);
        cost = N * c_sz[c_root] - calc_cost(root);
        // debug(i, H[i], root, cost, cost - H[i]);
        chmax(ans, cost - H[i]);
    }
    cout << ans << "\n";
}

int32_t main() {
    fastIO();

    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}