환승역 찾기 게임

시간 제한2초메모리 제한1024 MB

요약

트리의 각 정점에 색이 칠해져 있을 때, 모든 색에 대해 같은 색 두 정점 사이의 최단 경로에 놓이는 정점의 개수를 구합니다.

문제

Semia와 Hanbyeol은 환승역 찾기 게임을 하려고 한다.

환승역 찾기 게임은 트리로 이루어진 게임판에서 두 사람이 번갈아 가며 환승역을 찾는 게임이다. 트리의 모든 정점은 $1$ 부터 $K$ 까지의 색깔 중 하나로 칠해져 있다.

정점 $p$ 가 노선 $i$ 위에 있다는 것은, 색이 $i$ 인 서로 다른 두 정점 $a$ , $b$ 가 존재하여 둘을 잇는 유일한 최단 경로 위에 $p$ 가 있다는 뜻이다. $a$ , $b$ 중 하나가 $p$ 인 경우도 포함한다.

또, 정점 $p$ 가 노선 $1, 2, \cdots, K$ 모두의 위에 있으면 $p$ 를 환승역이라고 한다.

환승역 찾기 게임에서는 모든 환승역을 찾고 더 이상 환승역이 없다고 선언하면 높은 점수를 받는다. 그래서 두 사람은 게임판에 있는 환승역의 개수를 알고 싶어졌다. 두 사람을 도와 환승역의 개수를 구하자.

첫째 줄에 트리의 정점 개수 $N$ 과 색깔의 종류 $K$ 가 주어진다.

둘째 줄에는 각 정점에 칠해진 색깔 $A_i$ 가 공백으로 구분되어 주어진다.

다음 $N-1$ 개의 줄에는 트리에서 연결된 두 정점의 번호가 공백으로 구분되어 주어진다.

첫째 줄에 환승역의 개수를 출력한다.