CEZAR


Submit solution

Points: 20
Time limit: 1.0s
Memory limit: 493M

Problem type

Tại TP, có tất cả n thượng nghị sĩ ở trong n ngôi nhà (đánh số từ 1 đến n), giữa hai ngôi nhà có một đường đi duy nhất: đường đi trực tiếp hoặc không trực tiếp (đi qua các con đường khác). Tất cả các ngôi nhà đều đi được đến nhau. Mỗi thượng nghị sĩ khi đi từ nhà mình đến thượng viện, phải trả 1 USD khi đi qua một con phố (con phố là đường nối trực tiếp hai ngôi nhà bất kỳ).

Người đứng đầu thượng viện đã nghĩ cách làm sao cho số tiền mà các thượng nghị sĩ phải trả là tối thiểu. Vì vậy, ông ra quyết định:

  • Có k con phố miễn phí (thượng nghị sĩ sẽ không phải trả tiền khi đi trên con phố này).

  • Đặt tòa nhà thượng viện ở một trong n ngôi nhà.

Yêu cầu: Hãy viết chương trình tính xem chi phí tối thiểu là bao nhiêu?

Dữ liệu:

  • Dòng 1: Số nguyên n và k tương ứng là số ngôi nhà ở TP và số con phố miễn phí.

  • n – 1 dòng tiếp theo, mỗi dòng chứa 2 số i, j có nghĩa là có con phố nối ngôi nhà i và ngôi nhà j. (1< n ≤ 10000; 0 < k < n ; 1≤ i, j ≤ n ; i ≠ j)

Kết quả:

Một số duy nhất là chi phí tối thiểu phải trả.

Sample INput

13 3 
1 2 
2 3 
2 8 
7 8 
7 5
5 4
5 6
8 9 
8 10 
10 11 
10 12 
10 13

Sample Output

11

Ràng buộc

• Có 30% số test ứng với 30% số điểm của bài có n ≤ 30
• Có 40% số test ứng với 40% số điểm của bài có 30 < n ≤ 5000 
• Có 30% số test ứng với 30% số điểm của bài có 5000 < n ≤ 10000.

Comments

There are no comments at the moment.