25350번 - 환승역 찾기 게임

문제

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$개의 줄에는 트리 상에서 연결된 두 정점의 번호가 공백으로 구분되어 주어진다.

출력

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

제한

• 2ドル \leq N \leq 100,000$
• 1ドル \leq K \leq 50,000$
• 1ドル \leq A_i \leq K$

힌트