← 返回题目列表

AtCoder · abc397_e

H. 树的路径分解

中文机器翻译题面 查看原题

分数: 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