Caminhos

Temos uma árvore de $N$ vértices numerados de $1$ até $N$. A i-ésima aresta liga os vértices $U$ e $V$. Além disso, cada vértice é pintado em uma cor e a cor do vértice $i$ é $C_i$. Aqui, a cor de cada vértice é representada por um número inteiro entre $1$ e $N$ (inclusive). O mesmo número inteiro corresponde à mesma cor; números inteiros diferentes correspondem a cores diferentes.

Para cada $K = 1, 2, ..., N$, resolva o seguinte problema:

• Encontre o número de caminhos simples que passam por um vértice pintado na cor $K$ uma ou mais vezes.

Nota: Os caminhos simples de $U$ pra $V$ e de $V$ pra $U$ não são diferentes.

Entrada:

Na primeira linha da entrada será dado o inteiro $N$, a quantidade de vértices da árvore. Na segunda linha, $N$ inteiros $C_i$ serão dados, as cores dos vértices. Nas $N-1$ linhas seguintes, serão dadas as arestas da árvore.

Saída

Imprima a resposta para $K = 1, 2, ..., N$, em ordem, cada um em sua própria linha.

Restrições:

• $1 \leq N \leq 2*10^5$.
• $1 \leq C_i \leq N$.
• $1 \leq U, V \leq N$.
• O grafo dado é uma árvore.
• Todos os valores na entrada são inteiros.

Exemplos:

3
1 2 1
1 2
2 3

5
4
0

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

5
8
10
5
5

Para submeter sua solução, use esse link.