//DUEL
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
cout<<w.size()<<en;
for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
if (w.size()) cout<<w[w.size()-1]<<en;
if (fl) cout<<flush;
}
void M998()
{
swap(MOD,MOD2);
}
ll raand()
{
ll a=rund();
a*=RAND_MAX;
a+=rund();
return a;
}
#define rand raand
ll raaand()
{
return raand()*(MOD-7)+raand();
}
string to_upper(string a)
{
for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
return a;
}
string to_lower(string a)
{
for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
return a;
}
ll sti(string a,int base=10)
{
ll k=0;
for (int i=0;i<(int)a.size();++i)
{
k*=base;
k+=a[i]-'0';
}
return k;
}
template<class T>
void eras(vector<T>& a,T b)
{
a.erase(find(a.begin(),a.end(),b));
}
string its(ll k,int base=10)
{
if (k==0) return "0";
string a;
while (k)
{
a.push_back((k%base)+'0');
k/=base;
}
reverse(a.begin(),a.end());
return a;
}
ll min(ll a,int b)
{
if (a<b) return a;
return b;
}
ll min(int a,ll b)
{
if (a<b) return a;
return b;
}
ll max(ll a,int b)
{
if (a>b) return a;
return b;
}
ll max(int a,ll b)
{
if (a>b) return a;
return b;
}
ll gcd(ll a,ll b)
{
if (b==0) return a;
return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
template<class T,class K>
pair<T,K> mp(T a,K b)
{
return make_pair(a,b);
}
inline int mult(ll a,ll b)
{
return (a*b)%MOD;
}
inline int pot(int n,int k)
{
if (k==0) return 1;
ll a=pot(n,k/2);
a=mult(a,a);
if (k%2) return mult(a,n);
else return a;
}
int divide(int a,int b)
{
return mult(a,pot(b,MOD-2));
}
inline int sub(int a,int b)
{
if (a-b>=0) return a-b;
return a-b+MOD;
}
inline int add(int a,int b)
{
if (a+b>=MOD) return a+b-MOD;
return a+b;
}
bool prime(ll a)
{
if (a==1) return 0;
for (int i=2;i<=round(sqrt(a));++i)
{
if (a%i==0) return 0;
}
return 1;
}
const int N=100010,M=1<<17;
int n,li[N],par[N],st[N],cha[N],ss[N],cch,ind[N],cuin,u[N],v[N];
bool bio[N];
vi ch[N];
set<pair<pii,int>> s[N];
int seg[M*2+10];
void dfs1(int i)
{
bio[i]=1;
ss[i]=1;
for (auto a: ch[i]) if (!bio[a]) par[a]=i,dfs1(a),ss[i]+=ss[a];
}
void dfs2(int i)
{
bio[i]=1;
cha[i]=cch;
ind[i]=cuin++;
s[cch].insert({{ind[i],1},li[i]});
vector<pii> v;
for (auto a: ch[i]) if (!bio[a]) v.eb(ss[a],a);
sort(all(v));
reverse(all(v));
if (v.size())
{
dfs2(v[0].y);
}
//cout<<"node "<<i<<' '<<li[i]<<' '<<cha[i]<<en;
//for (auto a: v) cout<<a.x<<' '<<a.y<<en;
for (int j=1;j<v.size();++j)
{
++cch;
cuin=0;
st[cch]=v[j].y;
dfs2(v[j].y);
}
}
void upd(int i,int x)
{
for (i+=M;i;i/=2) seg[i]+=x;
}
int ge(int l,int r,int lo=0,int hi=M,int i=1)
{
if (lo>=l && hi<=r) return seg[i];
if (lo>=r || hi<=l) return 0;
int mid=(lo+hi)/2;
return ge(l,r,lo,mid,i*2)+ge(l,r,mid,hi,i*2+1);
}
void comp()
{
set<int> s;
for (int i=1;i<=n;++i) s.insert(li[i]);
vi v(all(s));
for (int i=1;i<=n;++i) li[i]=lower_bound(all(v),li[i])-v.begin();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)+13893829);
cin>>n;
const bool DBG=0;
for (int i=1;i<=n;++i) cin>>li[i];
comp();
for (int i=1;i<n;++i)
{
int a,b;
cin>>a>>b;
ch[a].pb(b);
ch[b].pb(a);
u[i]=a;
v[i]=b;
}
dfs1(1);
memset(bio,0,sizeof(bio));
dfs2(1);
st[0]=1;
if (DBG) for (int i=0;i<=cch;++i)
{
cout<<"chain "<<i<<":\n";
for (auto a: s[i]) cout<<a.x.x<<' '<<a.x.y<<' '<<a.y<<en;
cout<<"start: "<<st[i]<<en;
}
for (int i=1;i<n;++i)
{
int x=u[i],y=v[i];
auto it=s[cha[x]].upper_bound({{ind[x],MOD},MOD});
--it;
auto a=*it;
int sz=ind[x]-a.x.x+1;
vector<pii> ve;
ve.eb(a.y,-sz);
if (DBG) cout<<x<<' '<<a.y<<' '<<sz<<en;
upd(a.y,sz);
ll ans=0;
while (it!=s[cha[x]].begin())
{
--it;
if (DBG) cout<<x<<' '<<(it->x.x)<<' '<<(it->x.y)<<' '<<(it->y)<<en;
ans+=ge(0,it->y)*it->x.y;
ve.eb(it->y,-it->x.y);
upd(it->y,it->x.y);
}
while (cha[x])
{
x=par[st[cha[x]]];
it=s[cha[x]].upper_bound({{ind[x],MOD},MOD});
--it;
a=*it;
sz=ind[x]-a.x.x+1;
ve.eb(a.y,-sz);
if (DBG) cout<<x<<' '<<a.y<<' '<<sz<<en;
ans+=ge(0,a.y)*sz;
upd(a.y,sz);
while (it!=s[cha[x]].begin())
{
--it;
if (DBG) cout<<x<<' '<<(it->x.x)<<' '<<(it->x.y)<<' '<<(it->y)<<en;
ans+=ge(0,it->y)*it->x.y;
ve.eb(it->y,-it->x.y);
upd(it->y,it->x.y);
}
}
for (auto z: ve) upd(z.x,z.y);
cout<<ans<<en;
x=u[i],y=v[i];
it=s[cha[x]].upper_bound({{ind[x],MOD},MOD});
--it;
a=*it;
s[cha[x]].erase(a);
sz=ind[x]-a.x.x+1;
if (a.x.y>sz) s[cha[x]].insert({{ind[x]+1,a.x.y-sz},a.y});
it=s[cha[x]].upper_bound({{ind[x],MOD},MOD});
while (it!=s[cha[x]].begin())
{
--it;
sz+=it->x.y;
s[cha[x]].erase(it);
it=s[cha[x]].upper_bound({{ind[x],MOD},MOD});
}
s[cha[x]].insert({{0,sz},li[y]});
while (cha[x])
{
x=par[st[cha[x]]];
it=s[cha[x]].upper_bound({{ind[x],MOD},MOD});
--it;
a=*it;
s[cha[x]].erase(a);
sz=ind[x]-a.x.x+1;
if (a.x.y>sz) s[cha[x]].insert({{ind[x]+1,a.x.y-sz},a.y});
it=s[cha[x]].upper_bound({{ind[x],MOD},MOD});
if (DBG) cout<<"MOD "<<x<<' '<<a.x.x<<' '<<a.x.y<<' '<<a.y<<en;
while (it!=s[cha[x]].begin())
{
--it;
sz+=it->x.y;
s[cha[x]].erase(it);
it=s[cha[x]].upper_bound({{ind[x],MOD},MOD});
}
s[cha[x]].insert({{0,sz},li[y]});
}
if (DBG)
{
cout<<"new s[0]:"<<en;
for (auto a: s[0]) cout<<a.x.x<<' '<<a.x.y<<' '<<a.y<<en;
cout<<en;
}
}
}
