P7215 [JOISC 2020] Capital

JOI Country is a huge nation.

JOI Country has $N$ towns, numbered from $1$ to $N$. These towns are connected by $N-1$ bidirectional roads. JOI Country also has $K$ cities, numbered from $1$ to $K$. Town $i$ belongs to city $C_i$. Now the Prime Minister of JOI Country, Mr. JOI the $114514$th, wants to choose one city as the capital. The city chosen as the capital must satisfy the following condition: from any town in the capital to any other town in the capital, it is possible to travel using only towns in the capital. However, there may be no city that satisfies this condition. Therefore, Mr. JOI the $114514$th will perform city merges. Merging city $x$ and city $y$ will move all towns in city $y$ into city $x$. Find the minimum number of merges needed so that a capital can be chosen.

The first line contains two integers $N, K$, representing the number of towns and the number of cities. The next $N-1$ lines each contain two integers $u, v$, representing a bidirectional edge. The next $N$ lines contain one integer each; the $i$-th of these lines contains $C_i$, meaning that town $i$ belongs to city $C_i$.

Output one integer in a single line, representing the minimum number of merges.

#### Explanation for Sample 1 You can merge cities $1$ and $3$, and then choose city $1$ as the capital. #### Subtasks |Subtask|Special Property|Score| |:-:|:-:|:-:| |$1$|$N \le 20$|$1$| |$2$|$N \le 2000$|$10$| |$3$|Each town is connected to at most two towns|$30$| |$4$|None|$59$| #### Constraints For $100\%$ of the testdata, $1 \le K, u, v \le N \le 2 \times 10^5$. It is guaranteed that starting from any town you can reach all other towns. Also, $1 \le C_i \le K$. #### Notes Translated from [The 19th Japanese Olympiad in Informatics Spring Training Camp](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) [Day4 A Capital](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day4/capital_city.pdf). Translated by ChatGPT 5