Ở một quốc gia nọ có N thành phố, các thành phố được đánh số từ 1 đến N.
Có N - 1 con đường ở quốc gia này. Con đường thứ i kết nối hai thành phố u_i và thành phố v_i và cho phép di chuyển hai chiều. Với bất kỳ hai thành phố a và b nào trong quốc gia, ta luôn có thể di chuyển từ thành phố a đến thành phố b thông qua một số con đường trung gian.
Có một người đưa thư có nhiệm vụ giao một bức thư mật tới mọi thành phố trong quốc gia đó. Để làm được việc đó, người đưa thư chỉ cần truyền bức thư đó tới tối đa K thành phố. Giả sử người đưa thư hoàn thành việc đưa thư tại thời điểm 0. Khi đó với mọi thời điểm t = 1, 2, 3, ..., quy tắc sau được áp dụng:
- Với mọi thành phố a và b được kết nối với nhau trực tiếp bởi một con đường nào đó, nếu a đã nhận được bức thư tại thời điểm t - 0.5 và b chưa nhận được, thì b sẽ nhận được bức thư đó tại thời điểm t
Người đưa thư muốn chọn K thành phố để bắt đầu gửi thư sao cho tổng thời gian cần thiết để tất cả các thành phố đều nhận được thư là ít nhất. Hãy giúp người đưa thư xác định thời gian ngắn nhất cần thiết.
