#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 2e5 + 10, off = 1 << 20, maxcnt = 1e7;

int n, cnt;
set <int> s[maxn];
ll tour[maxcnt];
int prop[maxcnt];
int l[maxcnt];
int r[maxcnt];
int root[maxn];
vector <int> v;

void push(int x, int lo, int hi){
	if(x >= off || prop[x] == 0) return;
	
	int mid = (lo + hi) / 2;
	
	prop[x] = 0;
	tour[l[x]] = ((ll)mid - 1)*(mid - 1) - max(0LL, (ll)lo - 1)*(lo - 1) - tour[l[x]];
	tour[r[x]] = ((ll)hi - 1)*(hi - 1) - ((ll)mid - 1)*(mid - 1) - tour[r[x]];
	prop[l[x]] ^= 1;
	prop[r[x]] ^= 1;
}

void update(int x, int lo, int hi, int rig){
//	cout << x << ' ' << lo << ' ' << hi << ' ' << rig << ' ' << tour[x] << endl;
	
	if(l[x] == 0){
		cnt++;
		l[x] = cnt;
		cnt++;
		r[x] = cnt;
	}
	
	push(x, lo, hi);
	
	if(lo >= rig) return;
	
	if(hi <= rig){
		tour[x] = ((ll)hi - 1)*(hi - 1) - max(0LL, (ll)lo - 1)*(lo - 1) - tour[x];
		prop[x] ^= 1;
		return;
	}
	
	int mid = (lo + hi) / 2;
	update(l[x], lo, mid, rig);
	update(r[x], mid, hi, rig);
	
	tour[x] = tour[l[x]] + tour[r[x]];
}

ll query(int x, int lo, int hi, int lef, int rig){
	if(l[x] == 0){
		cnt++;
		l[x] = cnt;
		cnt++;
		r[x] = cnt;
	}
	
	push(x, lo, hi);
	
	if(hi <= lef || lo >= rig) return 0;
	
	if(lef <= lo && hi <= rig) return tour[x];
	
	int mid = (lo + hi) / 2;
	return query(l[x], lo, mid, lef, rig) + query(r[x], mid, hi, lef, rig);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		int a;
		cin >> a;
		a /= 2;
		
		cnt++;
		root[i] = cnt;
		s[i].insert(a);
		update(root[i], 0, off, a + 1);
	}
	
	for(int i = 1; i <= n - 1; i++){
		int a, b;
		cin >> a >> b;
		
		if(s[b].size() > s[a].size()) swap(a, b);
		
		v.clear();
		v.push_back(0);
		auto it = s[b].begin();
		while(it != s[b].end()){
			v.push_back(*it);
			it++;
		}
		s[b].clear();
		
		ll ans = 0;
		
//		cout << a << ' ' << b << endl;
		
		for(int j = v.size() - 1; j >= 1; j -= 2){
			
//			int q = query(root[a], 0, off, v[j - 1], v[j] + 1); 
//			cout << n + i << ' ' << v[j - 1] << ' ' << v[j] << ' ' << q << endl;
			
			ans += query(root[a], 0, off, v[j - 1] + 1, v[j] + 1);
		}
		
//		cout << tour[1] << endl;
		
		for(int j = 0; j < v.size(); j++){
			if(s[a].find(v[j]) == s[a].end()) s[a].insert(v[j]);
			else s[a].erase(v[j]);
			update(root[a], 0, off, v[j] + 1);
//			cout << v[j] << ' ' << "tour[1]: " << tour[1] << endl;
		}
		
		root[n + i] = root[a];
		swap(s[n + i], s[a]);
		   
		cout << ans * 4 << "\n";
	}
	
//	cout << root[7] << endl;
	
	return 0;
}