Đặt trạm phát sóng trên cây

Binary-search Buổi 13 — Chặt nhị phân đáp án greedy
Points
46
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Một mạng lưới gồm $N$ khu dân cư được kết nối với nhau thành một cây (gồm $N - 1$ cạnh, mỗi cạnh có độ dài $1$). Bạn được phép đặt tối đa $K$ trạm phát sóng tại các khu dân cư (mỗi trạm đặt tại một đỉnh của cây).

Nếu các trạm phát sóng có bán kính phủ sóng $D$, một khu dân cư sẽ nhận được tín hiệu nếu khoảng cách (số cạnh trên đường đi ngắn nhất) từ nó đến ít nhất một trạm phát sóng không vượt quá $D$. Hãy tìm bán kính $D$ nhỏ nhất để tất cả $N$ khu dân cư đều nhận được tín hiệu.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ thể hiện một cạnh nối giữa hai khu dân cư.
Dữ liệu ra

In ra bán kính $D$ nhỏ nhất tìm được.

Ví dụ
Input Output
7 2

1 2 1 3 2 4 2 5 3 6 3 7 | 1 | | 5 1 1 2 2 3 3 4 4 5 | 2 |

Giới hạn
  • $1 \le K \le N \le 10^5$
  • $1 \le u, v \le N$.
Draft saved