#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5, inf=1e9;
#define ll long long
ll n, u, v, t[nx], pa[nx], cnt, in[nx], out[nx], res, st, rid[nx];
vector<ll> d[nx];
void dfs(int u, int p)
{
pa[u]=p;
in[u]=++cnt;
rid[cnt]=u;
for (auto v:d[u]) if (v!=p) dfs(v, u);
out[u]=cnt;
}
struct segtree
{
ll lz[4*nx];
pair<ll, int> d[4*nx];
void pushlz(int l, int r, int i)
{
d[i].first+=lz[i];
if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
lz[i]=0;
}
void build(int l ,int r, int i)
{
if (l==r) return d[i]={t[rid[l]], rid[l]}, void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=max(d[2*i], d[2*i+1]);
}
void update(int l, int r, int i, int ql, int qr, ll vl)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return lz[i]=vl, pushlz(l, r, i), void();
int md=(l+r)/2;
update(l, md, 2*i, ql, qr, vl);
update(md+1, r, 2*i+1, ql ,qr ,vl);
d[i]=max(d[2*i], d[2*i+1]);
}
} s;
void solve(int u)
{
//if (++st>=10) return;
//cout<<"here "<<u<<' '<<in[u]<<' '<<out[u]<<' '<<res<<'\n';
s.update(1, n, 1, 1, n, -inf);
//cout<<"s "<<s.d[1].first<<' '<<s.d[1].second<<'\n';
for (auto v:d[u])
{
if (v==pa[u]) continue;
s.update(1, n, 1, in[v], out[v], inf);
//cout<<"debugv "<<u<<' '<<s.d[1].first<<' '<<s.d[1].second<<'\n';
if (s.d[1].first>0) res+=s.d[1].first+t[u], solve(s.d[1].second);
s.update(1, n, 1, in[v], out[v], -inf);
}
if (pa[u]!=-1)
{
if (in[u]>1) s.update(1, n, 1, 1, in[u]-1, inf);
if (out[u]<n) s.update(1, n, 1, out[u]+1, n, inf);
//cout<<"debug "<<u<<' '<<s.d[1].first<<' '<<s.d[1].second<<'\n';
if (s.d[1].first>0) res+=s.d[1].first+t[u], solve(s.d[1].second);
if (in[u]>1) s.update(1, n, 1, 1, in[u]-1, -inf);
if (out[u]<n) s.update(1, n, 1, out[u]+1, n, -inf);
}
s.update(1, n, 1, 1, n, inf);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n;
for (int i=1; i<=n; i++) cin>>t[i];
for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
dfs(1, -1);
//for (int i=1; i<=n; i++) cout<<"rid "<<i<<' '<<rid[i]<<'\n';
s.build(1, n, 1);
solve(s.d[1].second);
cout<<res;
}
