//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
if(b==0)return 1;
if(b==1)return(a%mod);
int tem=po(a,b/2);
if(b&1)return(((tem*tem)%mod)*a)%mod;
else return(tem*tem)%mod;
}
int GCD(int a,int b){
int x=0;
int ra,rb;
while(a&&b){
if(((a&1)==0)&&((b&1)==0)){
a>>=1,b>>=1,x++;
}
else if((a^b)&1){
if(a&1)b>>=1;
else a>>=1;
}
else{
ra=abs(a-b),rb=min(a,b);
a=ra,b=rb;
}
}
return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
struct link_cut_tree{
struct SPLAY{
int so[2],pa,v,si;
bool tg;
SPLAY():v(0),pa(0),tg(0),si(1){so[0]=so[1]=0;}
}splay[100010];
inline bool is_rt(int x){return splay[splay[x].pa].so[0]!=x&&splay[splay[x].pa].so[1]!=x;}
inline void push(int x){
if(splay[x].so[0])splay[splay[x].so[0]].v=splay[x].v;
if(splay[x].so[1])splay[splay[x].so[1]].v=splay[x].v;
if(splay[x].tg){
if(splay[x].so[0])splay[splay[x].so[0]].tg^=1;
if(splay[x].so[1])splay[splay[x].so[1]].tg^=1;
swap(splay[x].so[0],splay[x].so[1]);
splay[x].tg=0;
}
}
void push_all(int x){
if(!is_rt(x))push_all(splay[x].pa);
push(x);
}
inline void upd(int x){
splay[x].si=1;
if(splay[x].so[0])splay[x].si+=splay[splay[x].so[0]].si;
if(splay[x].so[1])splay[x].si+=splay[splay[x].so[1]].si;
}
inline void rotate(int x){
int y=splay[x].pa,z=splay[y].pa,d=splay[y].so[1]==x;
splay[x].pa=z;
if(!is_rt(y))splay[z].so[splay[z].so[1]==y]=x;
splay[splay[x].so[1^d]].pa=y;
splay[y].so[d]=splay[x].so[1^d];
splay[x].so[1^d]=y;
splay[y].pa=x;
upd(y);
upd(x);
}
inline void Splay(int x){
push_all(x);
while(!is_rt(x)){
int y=splay[x].pa;
if(!is_rt(y)){
int z=splay[y].pa;
if((splay[y].so[0]==x)^(splay[z].so[0]==y))rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline vector<pii> access(int x,int vl){
int la=0;
vector<pii> re;
while(x){
Splay(x);
splay[x].so[1]=0;
upd(x);
re.pb({splay[x].v,splay[x].si});
splay[x].so[1]=la;
splay[la].pa=x;
upd(x);
la=x;
x=splay[x].pa;
}
splay[la].v=vl;
return re;
}
inline void link(int x,int y){
splay[y].pa=x;
}
}LCT;
vector<int> ve;
map<int,int> m;
int a[100010],balbit[100010];
void ADD(int x,int v){
for(;x<=100001;x+=(x&(-x)))balbit[x]+=v;
}
int QRY(int x){
int re=0;
for(;x>0;x-=(x&(-x)))re+=balbit[x];
return re;
}
signed main(){
IOS();
int n;
cin>>n;
F(n)cin>>a[i],ve.pb(a[i]);
sort(all(ve));
ve.resize(unique(all(ve))-ve.begin());
F(sz(ve))m[ve[i]]=i+1;
F(n)a[i]=m[a[i]];
LCT.splay[1].v=a[0];
F(n-1){
int x,y;
cin>>x>>y;
vector<pii> tmp;
tmp=LCT.access(x,a[y-1]);
int ans=0;
for(pii pi:tmp){
ans+=pi.Y*QRY(pi.X-1);
bug(pi.X,pi.Y);
ADD(pi.X,pi.Y);
}
for(pii pi:tmp){
ADD(pi.X,-pi.Y);
}
LCT.splay[y].v=a[y-1];
LCT.link(x,y);
cout<<ans<<endl;
}
return 0;
}
