分数: 475 点
问题陈述
你得到了一棵树 NK 顶点。顶点已编号 1,2,\dots,NK,以及 i第边缘 (i=1,2,\dots,NK-1) 连接顶点 u_i 和 v_i 双向。
判断这棵树是否可以分解为 N 路径,每个长度 K。更准确地说,判断是否存在 N \times K 矩阵 P 满足以下条件:
- P_{1,1}, \dots, P_{1,K}, P_{2,1}, \dots, P_{N,K} 是一个排列 1,2,\dots,NK.
- 对于每个 i=1,2,\dots,N 和 j=1,2,\dots,K-1,有一条边连接顶点 P_{i,j} 和 P_{i,j+1}.
约束
- 1 \leq N
- 1 \leq K
- NK \leq 2 \times 10^5
- 1 \leq u_i < v_i \leq NK
- 给定的图是一棵树。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K
u_1 v_1
u_2 v_2
\vdots
u_{NK-1} v_{NK-1}
输出
如果可以将树分解为 N 每个长度的路径 K,打印 Yes。否则,打印 No.
示例输入 1
3 2 1 2 2 3 3 4 2 5 5 6
示例输出 1
Yes
可以分解为有顶点的路径 1,2,带有顶点的路径 3,4,以及带有顶点的路径 5,6.
示例输入 2
3 2 1 2 2 3 3 4 2 5 3 6
示例输出 2
No