n хот, тэдгээрийн хооронд n−1 зам бий. Аль ч хоёр хотын хооронд цорын ганц зам байдаг бөгөөд тэдгээрийн зай нь тухайн зам дээрх замуудын тоо юм.
Компани зарим хотуудад оффис нээхийг хүсэж байна, гэхдээ ямар ч хоёр оффисын хоорондох зай дор хаяж d байх ёстой. Хамгийн ихдээ хэдэн оффис нээх боломжтой вэ?
Эхний мөрөнд n, d хоёр бүхэл тоо байна: хотын тоо болон хамгийн бага зай. Хотууд 1,2,…,n гэсэн дугаартай.
Дараа нь замуудыг илэрхийлсэн n−1 мөр байна. Мөр бүрт a, b хоёр бүхэл тоо байна: a, b хотуудын хооронд зам бий.
Эхлээд k бүхэл тоог хэвлэ: оффисын хамгийн их тоо. Дараа нь оффис байх хотуудыг хэвлэ. Ямар ч хүчинтэй хариулт хэвлэж болно.
5 3 1 2 2 3 3 4 3 5
2 1 4