|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||256 MB||6||5||5||83.333%|
There are N cities numbered from 1 to N and N − 1 highways numbered from 1 to N − 1 in the United States of JOI. The i-th highway (1 ≤ i ≤ N − 1) connects between the city Ai and the city Bi bidirectionally. One can travel between any two cities by using the highways.
Currently, the United States of JOI is constituted of K states numbered from 1 to K. The city j (1 ≤ j ≤ N) belongs to the state Sj. Any state has at least one city.
Mr. K, the president of the United States of JOI, is afraid of separation of this country. The United States of JOI is said to be separable if one can divide all cities into Group X and Group Y so that the following conditions are satisfied:
Mr. K is going to merge states to make the United States of JOI not separable. When he merges states, he chooses two states and unifies the states into a state. The cities belonging to the unified state are the cities belonging to either of the two states. Mr. K wants to make the United States of JOI not separable by merging states as few times as possible.
Note that if the United States of JOI has only one state, it is not separable.
Write a program which, given information about cities, highways and states, calculates the minimum number of mergers to make the United States of JOI not separable.
Read the following data from the standard input. All the values in the input are integers.
N K A1 B1 : AN−1 BN−1 S1 : SN
Write the minimum number of mergers to make the United States of JOI not separable to the standard output.
5 4 1 2 2 3 3 4 3 5 1 2 1 3 4
In this sample, at the initial situation, the United States of JOI is separable. For example, if one groups the cities 1, 2, 3 and 4 as Group X and the city 5 as Group Y, the conditions of separability are satisfied.
If Mr. K merges the state 3 and the state 4, the United States of JOI becomes not separable. So the answer is 1.
5 4 1 2 2 3 3 4 4 5 1 2 3 4 1
In this sample, at the initial situation, the United States of JOI is not separable. So the answer is 0.
2 2 1 2 1 2