#include using namespace std; struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init; typedef long long LL; typedef vector V; typedef vector E; typedef vector VL; typedef vector Graph; #define rep(i,n) for (auto i = 0; i < n; i++) #define all(it,v) for(auto &it:v) #define pb push_back void make_tree(int v, Graph &G, E &P,Graph &C) { all(to, G[v]) { if (to != P[v]) { C[v].pb(to); P[to] = v; make_tree(to, G, P, C); } } } int main() { int N; while (cin >> N) { V val(N + 1), par(N, -1); rep(i, N)cin >> val[i]; val[N] = 0; Graph G(N), child(N); rep(i, N - 1) { int x, y; cin >> x >> y; x--, y--; G[x].pb(y); G[y].pb(x); } par[0] = N; make_tree(0, G, par, child); VL ds(N, 0); VL dl(N, 0), dl_p(N, 0), ds_p(N, 0); LL res = 0ll; std::function dfs = [&](int v) { map l, s; all(u, child[v]) { dfs(u); int x = val[u]; if (x > val[v]) l[x] = max(l[x], ds_p[u]); if (x < val[v]) s[x] = max(s[x], dl_p[u]); } LL l_S = 0, s_S = 0; LL ln = (LL)l.size(); LL sn = (LL)s.size(); all(it, l)l_S += it.second; all(it, s)s_S += it.second; dl[v] = l_S + (ln)*(ln - 1) / 2; ds[v] = s_S + (sn)*(sn - 1) / 2; if (l.count(val[par[v]]))l_S -= l[val[par[v]]], ln--; if (s.count(val[par[v]]))s_S -= s[val[par[v]]], sn--; if (val[par[v]] > val[v])ln++; if (val[par[v]] < val[v])sn++; if (val[par[v]] != val[v]) { dl_p[v] = l_S + (ln)*(ln - 1) / 2; ds_p[v] = s_S + (sn)*(sn - 1) / 2; } }; dfs(0); rep(i, N) { res = max({ res, dl[i],ds[i] }); if (i) res = max({ res,dl_p[i],ds_p[i] }); } cout << res << endl; } return 0; }