문제
SUDO 국은 N개의 마을로 이루어진 트리 형태의 국가이다. 현재, 1부터 K까지의 정수로 표현된 K개의 도시로 나누어져 있으며 j번째 마을은 Cj의 도시에 속한다. 또한, 각 도시가 적어도 하나의 마을을 포함하고 있음이 보장된다.
SUDO 국의 국왕인 준혁이는 하나의 도시를 국가의 수도로 고르려 한다. 이 때, 수도는 수도에 포함되는 마을들만을 이용하여 수도의 임의의 두 도시간의 이동이 가능해야 한다.
현재 이러한 조건을 만족하는 도시가 존재하지 않을 수도 있기 때문에, 준혁이는 두 도시를 합치는 작업을 하려 한다. 두 도시 x, y를 합친다는 의미는 x에 속하는 모든 마을을 y에 속하도록 만든다는 것이다. 현재 도시의 상황이 주어졌을 때 수도를 선정할 수 있도록 합치는 작업의 횟수를 최솟값을 구하여라.
입력
첫 번째 줄에 N, K가 공백을 사이에 두고 주어집니다.
두 번째 줄부터 N-1개의 줄에 트리의 간선의 정보가 주어진다.
세 번째 줄부터 N개의 줄에 각 마을이 속하는 도시 Cj가 주어진다.
1 ≤ N ≤ 200 000.
1 ≤ K ≤ N.
1 ≤ Ai ≤ N (1 ≤ i ≤ N − 1).
1 ≤ Bi ≤ N (1 ≤ i ≤ N − 1).
1 ≤ Cj ≤ K (1 ≤ j ≤ N).
Subtask 1 : N<=20
Subtask 2: N<=2000
Subtask 3: 트리의 모든 정점은 최대 2개의 다른 정점과 이어져 있다.
Subtask 4 : 추가 제한 조건 없음
출력
첫 번째 줄에 정답을 출력한다.
예제 #1
6 3
2 1
3 5
6 2
3 4
2 3
1
3
1
2
3
2
1
예제 #2
12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4
2
로그인해야 코드를 작성할 수 있어요.