Distinct colors - MarisaOJ: Marisa Online Judge

Given a tree of

n

$n$ vertices rooted at

1

$1$ , vertex

i

$i$ has color

A_{i}

$A_i$ . For each vertex

u

$u$ , count the number of distinct colors in the subtree rooted at

u

$u$ . ### Input - The first line contains an integers

n

$n$ . - The second line contains

n

$n$ integers

A_{i}

$A_i$ . - The next

n - 1

$n - 1$ lines, each line contains two integers

u, v

$u, v$ , there is an edge between

u

$u$ and

v

$v$ . ### Output - Print

n

$n$ integers, the

i^{t h}

$i^{th}$ is the answer for vertex

i

$i$ . ### Constraints -

1 \leq n \leq 10^{5}

$1 \le n \le 10^5$ . -

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

$1 \le A_i \le 10^5$ . -

1 \leq u, v \leq n

$1 \le u, v \le n$ . ### Example Input:

41222122324

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

Output:

2111

$2 1 1 1$

Topic

Tree

DSU

Rating

1400

Source

CSES

Solution (0)

Solution