시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 512 MB97322833.735%

문제

There are N towns in JOI Kingdom, numbered from 1 to N. There are N − 1 roads connecting towns. The i-th road (1 ≤ i ≤ N − 1) connects the town Ai and the town Bi. Every road can be passed through in either direction. You can travel from any town to any other town using some roads.

Currently, JOI Kingdom is divided into K cities, numbered from 1 to K. The town j (1 ≤ j ≤ N) belongs to the city Cj. Every city contains at least one town.

President K is the king of JOI Kingdom. He will choose one city as the capital city. For security reasons, the capital city must satisfy the following condition.

You can travel from any town in the capital city to any other town in the capital city by passing only through towns which belong to the capital city.

However, President K noticed that it might be the case that no city satisfies this condition and he is not able to choose the capital city.

In order to treat this problem, President K will merge cities. Precisely, he can do the following operation.

Choose x and y satisfying 1 ≤ x ≤ K, 1 ≤ y ≤ K and x , y, and change the cities of towns belonging to the city y so that every town belonging to the city y becomes a town belonging to the city x.

Since it costs too much to merge cities, President K would like to minimize the number of times to merge cities, to choose any city as the capital city.

Write a program which, given the structure of the towns and the roads in JOI Kingdom and the cities each town currently belongs, calculates the minimum number of merging cities.

입력

Read the following data from the standard input. All the values in the input are integers.

N K
A1 B1
.
.
.
AN−1 BN−1
C1
.
.
.
CN

출력

Write one line to the standard output. Output the minimum number of merging cities needed to choose a capital city.

제한

  • 1 ≤ N ≤ 200 000.
  • 1 ≤ K ≤ N.
  • 1 ≤ Ai ≤ N (1 ≤ i ≤ N − 1).
  • 1 ≤ Bi ≤ N (1 ≤ i ≤ N − 1).
  • You can travel from any town to any other town using some roads.
  • 1 ≤ Cj ≤ K (1 ≤ j ≤ N).
  • For every k (1 ≤ k ≤ K), there exists an integer j (1 ≤ j ≤ N) with Cj = k.

서브태스크

번호배점제한
11

N ≤ 20.

210

N ≤ 2 000.

330

Every town is directly connected to at most two towns by roads.

459

No additional constraints.

예제 입력 1

6 3
2 1
3 5
6 2
3 4
2 3
1
3
1
2
3
2

예제 출력 1

1

In Sample Input 1, for example, you merge the city 3 and the city 1, choosing (x, y) = (1, 3). Then you can choose the city 1 as the capital city. Initially, you cannot choose any city as the capital city. Thus the minimum number of merging cities is 1.

예제 입력 2

8 4
4 1
1 3
3 6
6 7
7 2
2 5
5 8
2
4
3
1
1
2
3
4

예제 출력 2

1

예제 입력 3

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

예제 출력 3

2

채점 및 기타 정보

  • 예제는 채점하지 않는다.