#2228. Wells

    ID: 2228 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>TEAM赛事:contest1729来源:qoj.ac数据:公开样例树上算法深搜

Wells

Wells

题目描述

CEOI 2021 – Day 2 Task Wells September 4th 2021 10 seconds / 1024 MiB / 100 points Task: Wells On the beautiful mountain of Velebit there are N shelters. Exactly N −1 pairs of shelters are connected by a hiking path such that it is possible to travel between any pair of shelters using these paths. Vila the Fairy likes hiking very much and it takes her exactly one day to traverse a hiking path connecting two shelters. She can use her magical abilities to appear at any shelter at the beginning of a day, and then spend the next K −1 days hiking in such a way that she never visits the same shelter more than once. Thus, during her hike, Vila visits exactly K shelters. Vila gets thirsty while hiking so she would like some shelters to have water wells. During any possible hike of hers she wants to visit exactly one shelter with a well. Your task is to determine whether it is possible to find a subset of shelters at which to put wells to satisfy Vila’s peculiar wishes. In addition, you need to calculate the number of such subsets modulo 109 + 7. Formally, given a tree of N vertices and a positive integer K, determine if there is a subset of vertices such that any path containing exactly K vertices has exactly one vertex from the subset. Additionally, you are asked to find the number of such subsets modulo 109 + 7. Input The first line contains two integers N and K (2 ≤K ≤N) from the task description. The next N −1 lines describe the hiking paths. The i-th of these lines contains two space-separated integers ai and bi (1 ≤ai, bi ≤N), representing a hiking path between shelters ai and bi. It is guaranteed that these paths form a tree. Output On the first line, output "YES" if there exists a subset of shelters satisfying Vila’s conditions and "NO", otherwise. On the second line output the number of possible subsets of shelters satisfying Vila’s conditions modulo 109 + 7. Scoring Subtask Score Constraints 1 30 2 ≤K ≤N ≤200 2 20 2 ≤K ≤N ≤10 000 3 20 2 ≤K ≤N ≤500 000 4 30 2 ≤K ≤N ≤1 500 000 If your program outputs the correct first line, but does not provide the correct second line, that test case will be scored with 60% of points allocated for the subtask it is part of. The score for each subtask equals the smallest score obtained by one of its test cases. 5 of 6 CEOI 2021 – Day 2 Task Wells September 4th 2021 10 seconds / 1024 MiB / 100 points Examples input input input 4 2 8 3 6 5 3 4 7 3 4 1 3 1 1 3 4 2 2 3 7 8 3 6 5 1 5 2 output 4 6 4 6 7 2 YES output 3 6 2 YES output 10 NO 0 Clarification of the first example: The valid subsets of shelters are {3} and {1, 2, 4}. Clarification of the third example: There is only one path of length 5, and that path contains nodes 3, 6, 4, 2, and 5. Exactly one of these nodes must be in a sought subset, and it makes no difference whether node 1 is in the subset. Therefore, the valid subsets of shelters are {3}, {1, 3}, {6}, {1, 6}, {4}, {1, 4}, {2}, {1, 2}, {5}, {1, 5}. 6 of 6

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 2
3 4
3 1
2 3
YES
2
6 5
8 3
4 1
7 3
1 3
4 2
3 6
7 8
5 1
5 2
4 6
4 6
7 2
3 6
YES
10
NO
0