Colorful path - MarisaOJ: Marisa Online Judge

For a tree with

n

$n$ vertices, color vertex

i

$i$ with color

A_{i}

$A_i$ . Define

f (x, y)

$f(x, y)$ as the number of distinct colors on the simple path from

x

$x$ to

y

$y$ . For each vertex

i

$i$ from

1

$1$ to

n

$n$ , calculate

\sum_{j = 1}^{n} f (i, j)

$\sum_{j=1}^{n} f(i, j)$ . ### Input - The first line contains an integer

n

$n$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The next

n - 1

$n-1$ lines each contain two integers

u, v

$u, v$ indicating an edge between vertices

u

$u$ and

v

$v$ . ### Output - Output

n

$n$ integers, where the

i

$i$ -th integer is

\sum_{j = 1}^{n} f (i, j)

$\sum_{j=1}^{n} f(i, j)$ . ### Constraints -

1 \leq n, A_{i} \leq 10^{5}

$1 \le n, A_i \le 10^5$ . ### Example Input:

51232312232415

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

Output:

10911912

$10 9 11 9 12$

Topic

Graph

Tree

Rating

2100

Solution (0)

Solution