- Prepare
- Data Structures
- Advanced
- Unique Colors

# Unique Colors

# Unique Colors

You are given an unrooted tree of nodes numbered from to . Each node has a color, .

Let be the number of different colors in the path between node and node . For each node , calculate the value of , defined as follows:

Your task is to print the value of for each node .

**Input Format**

The first line contains a single integer, , denoting the number of nodes.

The second line contains space-separated integers, , where each describes the color of node .

Each of the subsequent lines contains space-separated integers, and , defining an undirected edge between nodes and .

**Constraints**

**Output Format**

Print lines, where the line contains a single integer denoting .

**Sample Input**

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

**Sample Output**

```
10
9
11
9
12
```

**Explanation**

The *Sample Input* defines the following tree:

Each is calculated as follows: