#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i=0; i<n; ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
#define ll long long int

struct Eda{
	int l;
	unordered_map<int, int> d;//出た色と端からの距離
};

static unordered_map<int, bool> e[200000];
static Eda ed[200000];

int main(){
	int n;
	cin>>n;
	int c[200000];
	rep(i, n){
		cin>>c[i]; c[i]--;
	}
	rep(i, n-1){
		int a, b;
		cin>>a>>b; a--; b--;
		e[a][b]=true;
		e[b][a]=true;
	}

	rep(i, n){
		ed[i].l=1;
		ed[i].d[c[i]]=1;
	}

	ll mcnt[200000]={0};

	stack<int> s;
	rep(i, n) if(e[i].size()==1) s.push(i);
	if(!s.empty()) s.pop();

	while(!s.empty()){
		int u=s.top(); s.pop();
		if(e[u].size()==0){
			rep(c, n){
				int num= ed[u].l - ed[u].d[c];
				mcnt[c] += (ll)(num+1)*num/2;
			}
			break;
		}
		if(e[u].size()>1) continue;

		int v=e[u].begin()->first;
		e[u].erase(v);
		e[v].erase(u);

		int num= ed[u].l - ed[u].d[c[v]];
		mcnt[c[v]]+= (ll)(num+1)*num/2;
		ed[u].d[c[v]] = ed[u].l;

		//merge
		ed[v].l+=ed[u].l;
		if(ed[u].d.size() > ed[v].d.size()) swap(ed[u].d, ed[v].d);
		repit(it, ed[u].d){
			ed[v].d[it->first] += it->second;
		}

		s.push(v);
	}

	ll allpat=(ll)(n+1)*n/2;
	rep(i, n) cout << (allpat-mcnt[i]) << endl;
	return 0;
}

### Prompt

Create a solution in CPP for the following problem:

We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i. Additionally, each vertex is painted in a color, and the color of Vertex i is c_i. Here, the color of each vertex is represented by an integer between 1 and N (inclusive). The same integer corresponds to the same color; different integers correspond to different colors.

For each k=1, 2, ..., N, solve the following problem:

* Find the number of simple paths that visit a vertex painted in the color k one or more times.



Note: The simple paths from Vertex u to v and from v to u are not distinguished.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 1 \leq c_i \leq N
* 1 \leq a_i,b_i \leq N
* The given graph is a tree.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
c_1 c_2 ... c_N
a_1 b_1
:
a_{N-1} b_{N-1}


Output

Print the answers for k = 1, 2, ..., N in order, each in its own line.

Examples

Input

3
1 2 1
1 2
2 3


Output

5
4
0


Input

1
1


Output

1


Input

2
1 2
1 2


Output

2
2


Input

5
1 2 3 4 5
1 2
2 3
3 4
3 5


Output

5
8
10
5
5


Input

8
2 7 2 5 4 1 7 5
3 1
1 2
2 7
4 5
5 6
6 8
7 8


Output

18
15
0
14
23
0
23
0

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i=0; i<n; ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
#define ll long long int

struct Eda{
	int l;
	unordered_map<int, int> d;//出た色と端からの距離
};

static unordered_map<int, bool> e[200000];
static Eda ed[200000];

int main(){
	int n;
	cin>>n;
	int c[200000];
	rep(i, n){
		cin>>c[i]; c[i]--;
	}
	rep(i, n-1){
		int a, b;
		cin>>a>>b; a--; b--;
		e[a][b]=true;
		e[b][a]=true;
	}

	rep(i, n){
		ed[i].l=1;
		ed[i].d[c[i]]=1;
	}

	ll mcnt[200000]={0};

	stack<int> s;
	rep(i, n) if(e[i].size()==1) s.push(i);
	if(!s.empty()) s.pop();

	while(!s.empty()){
		int u=s.top(); s.pop();
		if(e[u].size()==0){
			rep(c, n){
				int num= ed[u].l - ed[u].d[c];
				mcnt[c] += (ll)(num+1)*num/2;
			}
			break;
		}
		if(e[u].size()>1) continue;

		int v=e[u].begin()->first;
		e[u].erase(v);
		e[v].erase(u);

		int num= ed[u].l - ed[u].d[c[v]];
		mcnt[c[v]]+= (ll)(num+1)*num/2;
		ed[u].d[c[v]] = ed[u].l;

		//merge
		ed[v].l+=ed[u].l;
		if(ed[u].d.size() > ed[v].d.size()) swap(ed[u].d, ed[v].d);
		repit(it, ed[u].d){
			ed[v].d[it->first] += it->second;
		}

		s.push(v);
	}

	ll allpat=(ll)(n+1)*n/2;
	rep(i, n) cout << (allpat-mcnt[i]) << endl;
	return 0;
}

```