CEOI 2021 - Wells
Xem PDFĐề bài
Trên ngọn núi Velebit xinh đẹp có \(N\) trạm trú ẩn. Có đúng \(N-1\) cặp trạm được nối bằng đường mòn sao cho có thể đi giữa mọi cặp trạm bằng các đường mòn này.
Nàng tiên Vila rất thích đi bộ đường dài. Cô mất đúng một ngày để đi qua một đường mòn nối hai trạm. Nhờ phép thuật, Vila có thể xuất hiện tại một trạm bất kỳ vào đầu ngày, rồi dành \(K-1\) ngày tiếp theo để đi bộ sao cho không đến cùng một trạm quá một lần. Như vậy, trong chuyến đi, Vila ghé đúng \(K\) trạm.
Vila khát nước khi đi bộ nên muốn một số trạm có giếng nước. Trong mọi chuyến đi có thể thực hiện, cô muốn ghé đúng một trạm có giếng.
Nhiệm vụ của bạn là xác định có thể chọn một tập con các trạm để đặt giếng thỏa mãn mong muốn đặc biệt của Vila hay không. Ngoài ra, hãy tính số tập con như vậy theo modulo \(10^9+7\).
Nói cách khác, cho một cây có \(N\) đỉnh và số nguyên dương \(K\), hãy xác định có tồn tại một tập con các đỉnh sao cho mọi đường đi chứa đúng \(K\) đỉnh đều chứa đúng một đỉnh thuộc tập con hay không, đồng thời đếm số tập con như vậy theo modulo \(10^9+7\).
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(2\le K\le N\)).
\(N-1\) dòng tiếp theo mô tả các đường mòn. Dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) (\(1\le a_i,b_i\le N\)), cho biết có một đường mòn nối hai trạm \(a_i\) và \(b_i\).
Các đường mòn được bảo đảm tạo thành một cây.
Dữ liệu ra
Dòng đầu tiên in YES nếu tồn tại một tập con các trạm thỏa mãn điều kiện của Vila; ngược lại, in NO.
Dòng thứ hai in số tập con thỏa mãn điều kiện theo modulo \(10^9+7\).
Chấm điểm
- Subtask 1 (30 điểm): \(2\le K\le N\le200\).
- Subtask 2 (20 điểm): \(2\le K\le N\le10\,000\).
- Subtask 3 (20 điểm): \(2\le K\le N\le500\,000\).
- Subtask 4 (30 điểm): \(2\le K\le N\le1\,500\,000\).
Nếu chương trình in đúng dòng đầu tiên nhưng dòng thứ hai không đúng, testcase đó nhận \(60\%\) số điểm của subtask chứa nó.
Điểm của mỗi subtask bằng điểm nhỏ nhất trong các testcase thuộc subtask đó.
Ví dụ
Ví dụ 1
Input
4 2
3 4
3 1
2 3Output
YES
2Giải thích
![Cây của ví dụ 1https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_80cacdd6.png
Các tập trạm hợp lệ là \(\{3\}\) và \(\{1,2,4\}\).
Ví dụ 2
Input
8 3
7 3
1 3
7 8
5 1
4 6
7 2
3 6Output
NO
0Giải thích
![Cây của ví dụ 2https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_962db33a.png
Ví dụ 3
Input
6 5
4 1
4 2
3 6
5 2
4 6Output
YES
10Giải thích
![Cây của ví dụ 3https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_7e12317d.png
Chỉ có một đường đi chứa \(5\) đỉnh, gồm các đỉnh \(3,6,4,2,5\). Tập cần tìm phải chứa đúng một trong các đỉnh này; việc có chứa đỉnh \(1\) hay không không ảnh hưởng.
Vì vậy, các tập trạm hợp lệ là \(\{3\}\), \(\{1,3\}\), \(\{6\}\), \(\{1,6\}\), \(\{4\}\), \(\{1,4\}\), \(\{2\}\), \(\{1,2\}\), \(\{5\}\) và \(\{1,5\}\).
Kỳ thi:
- CEOI 2021 - Ngày 2 (4 Tháng 9., 2021)
Bình luận