We will refer to the number of vertices in a connected component of the graph as the size of the connected component.

Let’s rephrase the problem as follows:

Choose a permutation \(P=(P_1,P_2,\dots,P_N)\) of integers from \(1\) to \(N\) uniformly at random. Initialize a counter \(X\) to \(X=0\), and perform the following for \(i=1,2,\dots,N\) in this order:

• If the size of the connected component containing vertex \(P_i\) is \(K+1\) or more, update \(X \leftarrow X+1\) and delete all edges with vertex \(P_i\) as an endpoint. Otherwise, do nothing.

Find the expected value of \(X\) after all operations.

Note that if we ignore the do-nothing operations, the next vertex to be operated on is chosen uniformly at random from the vertices belonging to connected components of size \(K+1\) or more.

Under this rephrasing, let’s consider how to calculate the answer. For a subtree \(T'\) of the graph, let \(p(T')\) be the probability that during the operations, there is a time that the connected component that contains \(p_i\) is \(T'\). By linearity of expectation, the answer is the sum of \(p(T')\) for \(T'\) with size \(K+1\) or more (you might want to consider, for example, the sum over the vertices \(v\) of the probabilities that the counter gets incremented during the operation, but considering that we eventually have to determine what connected component \(v\) belongs to, it is natural to think this way).

Let’s consider how to calculate \(p(T')\). Let \(n\) be the number of vertices in \(T'\), and \(m\) be the number of vertices directly connected to \(T'\) by an edge in the original tree. There will be a time that the connected component that contains \(v\) is \(T'\) if and only if the \(m\) vertices are chosen before the \(n\) vertices (regarding whether edge deletion occurs when the \(m\) vertices are chosen, we know that it will because they are connected to \(K+1 \leq n\) vertices at that moment). Therefore, we find that \(p(T')=\frac{n!m!}{(n+m)!}\).

From the above, the answer to the problem can be calculated if we can find, for each \(n\) and \(m\), the number of subtrees \(T'\) that contain \(n\) vertices and are directly connected to \(m\) vertices in the original tree. This can be found by tree DP, and performing the same analysis as the so-called square tree DP reveals that it takes \(O(N^2K^2)\) time, which is sufficiently fast (\(\Theta(N^3K^2)\) solutions may also pass since the constant factor is small).