#include <bits/stdc++.h>

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

using namespace std;

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

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;
ll pravi[maxn];
int arr[maxn];
vector <int> saz;

void push(int x, int lo, int hi){
	if(hi - lo == 1 || prop[x] == 0) return;
	
	int mid = (lo + hi) / 2;
	
	prop[x] = 0;
	tour[l[x]] = pravi[mid] - pravi[lo] - tour[l[x]];
	tour[r[x]] = pravi[hi] - pravi[mid] - 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] = pravi[hi] - pravi[lo] - 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++){
		cin >> arr[i];
		arr[i] /= 2;
		saz.push_back(arr[i]);
	}
	
	saz.push_back(0);
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());

	for(int i = 1; i <= n; i++){
		int poz = lower_bound(saz.begin(), saz.end(), arr[i]) - saz.begin();
		pravi[poz] = (ll)arr[i] * arr[i];
		arr[i] = poz;
		cnt++;
		root[i] = cnt;
		s[i].insert(arr[i]);
	}

	for(int i = 1; i < n; i++){
		update(root[i], 0, off, arr[i]);
	}
	
	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;
				
		for(int j = v.size() - 1; j >= 1; j -= 2){			
			ans += query(root[a], 0, off, v[j - 1], v[j]);
		}
		
		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]);
		}
		
		root[n + i] = root[a];
		swap(s[n + i], s[a]);
		   
		cout << ans * 4 << "\n";
	}
		
	return 0;
}