Background

Translated from CEOI 2021 Day 2 T3. Wells.

Abusing the judging resources will result in your account being banned.

Problem Description

Given a tree with $N$ nodes and a positive integer $K$, determine whether there exists a subset of vertices such that every path containing exactly $K$ vertices has exactly one vertex from this subset. Also, you need to find the number of such subsets modulo $10^9+7$ (output $0$ if none exist).

Input Format

The first line contains two integers $N$ and $K$.

The next $N-1$ lines each contain two integers $u$ and $v$, indicating that there is an undirected edge between node $u$ and node $v$.

Output Format

The first line contains a string: output YES if it exists, otherwise output NO.

The second line contains an integer, the number of subsets that satisfy the condition. If none exist, output $0$.

4 2
3 4
3 1
2 3

YES 
2

8 3
7 3
1 3
7 8
5 1
4 6
7 2
3 6

NO
0

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

YES
10

Hint

Sample Explanation 1

The subsets that satisfy the condition are: $\{3\}$, $\{1,2,4\}$.

Sample Explanation 2

Sample Explanation 3

There is only one path of length $5$, which contains nodes $3,6,4,2,5$. Among these nodes, there must be exactly one in the subset, and whether node $1$ is in the subset makes no difference.

Therefore, all subsets that satisfy the condition are: $\{3\}$, $\{1,3\}$, $\{6\}$, $\{1,6\}$, $\{4\}$, $\{1,4\}$, $\{2\}$, $\{1,2\}$, $\{5\}$, $\{1,5\}$.

Constraints and Notes

For $100\%$ of the testdata: $2\leq K\leq N\le 1.5\times 10^6$.

Translated by ChatGPT 5