P10531 [XJTUPC 2024] Christmas Tree

There is a tree with $n$ nodes, numbered from $1$ to $n$. Each node of the tree has a color, denoted by $col_i$. Different $col_i$ represent different colors. Little L wants to use this tree to make many Christmas trees. A connected component can be made into a Christmas tree if and only if it has at least $k$ different colors. Little L will split the tree into several pairwise disjoint connected components, and take those components that satisfy the condition to make Christmas trees. Given the shape of the tree, what is the maximum number of Christmas trees that can be made?

The first line contains two positive integers $n, k$ ($1\le k \le n \le 2\times 10^5$), separated by spaces. The second line contains $n$ positive integers $col_i$ ($1\le col_i \le n$), representing the color of node $i$, separated by spaces. The next $n-1$ lines each contain two positive integers $x, y$ ($1\le x,y \le n$, $x \neq y$), representing an edge in the tree, separated by spaces.

Output one line with one integer, representing your answer.

Translated by ChatGPT 5