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.