P8176 [CEOI 2021] Wells

Translated from CEOI 2021 Day 2 T3. [Wells](https://hsin.hr/ceoi/competition/ceoi2021_day2_tasks.pdf). **Abusing the judging resources will result in your account being banned.**

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).

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$.

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$.

#### 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$. | Subtask | Score | Constraints | | :-----: | :---: | :---------: | | $1$ | $30$ | $2\leq K\leq N\le 200$ | | $2$ | $20$ | $2\leq K\leq N\le 10^4$ | | $3$ | $20$ | $2\leq K\leq N\le 5\times 10^5$ | | $4$ | $30$ | $2\leq K\leq N\le 1.5\times 10^6$ | Translated by ChatGPT 5