#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define forn(i,n) for (int i=0;i<n;i++)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define trav(a,x) for (auto& a : x)

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define mem(x,a) memset(x,a,sizeof(x))

typedef vector<int> vi;
typedef pair<int,int> pii;

const int MOD = 1e9+7;
const int INF = 1e18;
const int N = 2e5 + 5;

int n , cnt[N] , sz[N] ,col[N] , ans[N];
vi g[N]; 
int f (int n){
 return (n * (n + 1))/2 ;
}
void dfs(int u , int par = 0){
 sz[u] = 1 ;
 int c = col[u] ;
 int temp = cnt[c] , delta = 0;

 trav(to , g[u]){
  if(to == par)continue;
  int last = cnt[c] ;
  dfs(to , u);
  delta = cnt[c] - last ;
  sz[u] += sz[to] ;

  ans[c] += f(sz[to] - delta) ;
 }
 cnt[c] =temp +  sz[u];
}
int32_t main()
{
 cin >> n ;
 // n++;
 rep(i,1 ,n + 1)cin >> col[i];
 forn(i,n-1){
  int u , v ;
  cin >> u >> v ;
  g[u].pb(v);
  g[v].pb(u);
 }
 dfs(1 , 0);

 rep(i , 1 , n + 1){
  cout << f(n) - ans[i] - f(n - cnt[i]) << endl ;
 }

 return 0;
}        
### Prompt

Please formulate a CPP solution to 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 int long long int
#define forn(i,n) for (int i=0;i<n;i++)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define trav(a,x) for (auto& a : x)

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define mem(x,a) memset(x,a,sizeof(x))

typedef vector<int> vi;
typedef pair<int,int> pii;

const int MOD = 1e9+7;
const int INF = 1e18;
const int N = 2e5 + 5;

int n , cnt[N] , sz[N] ,col[N] , ans[N];
vi g[N]; 
int f (int n){
 return (n * (n + 1))/2 ;
}
void dfs(int u , int par = 0){
 sz[u] = 1 ;
 int c = col[u] ;
 int temp = cnt[c] , delta = 0;

 trav(to , g[u]){
  if(to == par)continue;
  int last = cnt[c] ;
  dfs(to , u);
  delta = cnt[c] - last ;
  sz[u] += sz[to] ;

  ans[c] += f(sz[to] - delta) ;
 }
 cnt[c] =temp +  sz[u];
}
int32_t main()
{
 cin >> n ;
 // n++;
 rep(i,1 ,n + 1)cin >> col[i];
 forn(i,n-1){
  int u , v ;
  cin >> u >> v ;
  g[u].pb(v);
  g[v].pb(u);
 }
 dfs(1 , 0);

 rep(i , 1 , n + 1){
  cout << f(n) - ans[i] - f(n - cnt[i]) << endl ;
 }

 return 0;
}        
```