E - Path Decomposition of a Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 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

Score : 475 points

Problem Statement

You are given a tree with NK vertices. The vertices are numbered 1,2,\dots,NK, and the i-th edge (i=1,2,\dots,NK-1) connects vertices u_i and v_i bidirectionally.

Determine whether this tree can be decomposed into N paths, each of length K. More precisely, determine whether there exists an N \times K matrix P satisfying the following:

  • P_{1,1}, \dots, P_{1,K}, P_{2,1}, \dots, P_{N,K} is a permutation of 1,2,\dots,NK.
  • For each i=1,2,\dots,N and j=1,2,\dots,K-1, there is an edge connecting vertices P_{i,j} and P_{i,j+1}.

Constraints

  • 1 \leq N
  • 1 \leq K
  • NK \leq 2 \times 10^5
  • 1 \leq u_i < v_i \leq NK
  • The given graph is a tree.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
u_1 v_1
u_2 v_2
\vdots
u_{NK-1} v_{NK-1}

Output

If it is possible to decompose the tree into N paths each of length K, print Yes. Otherwise, print No.

Sample Input 1

3 2
1 2
2 3
3 4
2 5
5 6

Sample Output 1

Yes

It can be decomposed into a path with vertices 1,2, a path with vertices 3,4, and a path with vertices 5,6.

Sample Input 2

3 2
1 2
2 3
3 4
2 5
3 6

Sample Output 2

No