Chọn ĐTQG Huế 2026 - Hành trình đầy đủ
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Thành phố A đang chuẩn bị tổ chức một hội chợ lớn gồm ~N~ gian hàng được đánh số từ ~1~ đến ~N~. Giữa các gian hàng có đúng ~N-1~ con đường hai chiều kết nối trực tiếp, được thiết kế sao cho từ một gian hàng bất kỳ luôn tồn tại duy nhất một đường đi đơn đến một gian hàng khác mà không tạo thành chu trình.
Trên mỗi đường đi trực tiếp, ban tổ chức sẽ phát cho du khách một miếng dán lưu niệm loại ~1, 2, \dots, M~. Khi di chuyển qua một con đường, du khách sẽ thu thập được miếng dán trên con đường đó.
Một hành trình từ ~u_0=s~, đi qua các gian hàng trung gian ~u_1, u_2, \dots, u_{m-1}~, đến ~t=u_m~ được gọi là hành trình đầy đủ nếu thoả mãn các điều kiện sau:
Hành trình đi qua đúng ~M+1~ gian hàng, ~M~ con đường và mỗi gian hàng đi qua đúng một lần;
Trên hành trình đó, du khách phải thu thập đầy đủ ~M~ loại miếng dán lưu niệm, mỗi loại thu thập đúng một lần.
Yêu cầu: Hãy đếm xem có bao nhiêu hành trình đầy đủ như trên. Lưu ý: ta xem hành trình từ ~s~ đến ~t~ và từ ~t~ đến ~s~ là cùng một hành trình.
Input
Dòng ~1~: gồm hai số nguyên ~N~ và ~M~ ~(1 \le M < N \le 10^5)~.
Từ dòng ~2~ đến dòng ~N~: mỗi dòng gồm ba số nguyên dương ~u_j, v_j, c_j~ mô tả một con đường hai chiều nối gian hàng ~u_j~ và ~v_j~, và trên con đường này ban tổ chức phát cho du khách miếng dán loại ~c_j~.
Output
Một dòng duy nhất là số lượng hành trình đầy đủ.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~N \le 1000~. |
| 2 | ~20\%~ | ~M=2~. |
| 3 | ~20\%~ | ~M=3~. |
| 4 | ~20\%~ | Tồn tại một đường đi đi qua tất cả các gian hàng. |
| 5 | ~20\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
6 3
1 2 1
2 3 2
2 4 2
3 5 3
2 6 1
Sample Output 1
2
Notes
Hai hành trình đầy đủ là:
~1-2-3-5~ (các miếng dán thu thập được lần lượt là ~1, 2, 3~)
~5-3-2-6~ (các miếng dán thu thập được lần lượt là ~3, 2, 1~)
Bình luận