P3915 Tree Decomposition

Given a tree with $N$ vertices and an integer $K$, determine whether it can be partitioned into $\frac{N}{K}$ connected components, each containing exactly $K$ vertices.

The first line contains an integer $T$, the number of test cases. Then follow $T$ test cases: The first line of each test case contains two integers $N, K$. The next $N - 1$ lines each contain two integers $A_i, B_i$, denoting the edge $(A_i, B_i)$. The vertices are labeled $1, 2, \ldots, N$.

For each test case, output `YES` or `NO`.

- For $60\%$ of the testdata, $1 \le N, K \le 10^3$. - For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le N, K \le 10^5$. Translated by ChatGPT 5