색깔 있는 트리

정점에 색이 칠해진 트리가 주어진다. 각 간선에 대해, 같은 색을 가진 정점 쌍 중 두 정점 사이의 경로에 그 간선이 포함되는 쌍의 개수를 구하라. 트리에서는 임의의 두 정점을 잇는 경로가 정확히 하나뿐이다.

첫 줄에 정점의 개수 $n$ ($2 \le n \le 10^5$)이 주어진다. 정점은 1번부터 $n$번까지 번호가 매겨져 있다.

다음 $n$개의 줄에는 정수 $c$ ($1 \le c \le n$)가 한 줄에 하나씩 주어지며, 순서대로 각 정점의 색을 나타낸다.

다음 $n-1$개의 줄에는 두 정수 $a$, $b$ ($1 \le a < b \le n$)가 주어지며, 정점 $a$와 정점 $b$를 잇는 무방향 간선을 나타낸다.

$n-1$개의 줄에 답을 출력한다. 각 줄에는 입력에서 간선이 주어진 순서대로, 그 간선에 대한 답을 정수 하나로 출력한다.