P3915 树的分解

树的分解 P3915

by Youngsc

给出 $N$ 个点的树和 $K$，问能否把树划分成 $\frac{N}{K}$ 个连通块，且每个连通块的点数都是 $K$。

输入数据格式

第一行，一个整数 $T$，表示数据组数。接下来 $T$ 组数据，对于每组数据：

第一行，两个整数 $N, K$。

接下来 $N - 1$ 行，每行两个整数 $A_i, B_i$，表示边 $(A_i, B_i)$。点用 $1, 2, \ldots, N$ 编号。

输出数据格式

对于每组数据，输出 YES 或 NO。

输入输出样例

输入 #1	输出 #1
2 4 2 1 2 2 3 3 4 4 2 1 2 1 3 1 4	YES NO

说明与提示

• 对于 $60 \%$ 的数据，$1 \le N, K \le 10^3$；
• 对于 $100 \%$ 的数据，$1 \le T \le 10$，$1 \le N ,K \le 10^5$。

*练习笔记

暂无人完成练习，做第一个完成练习的人—-first blood ！