CSES - Creating Offices | Xây Dựng Văn Phòng
Xem PDF
Điểm:
600 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có \(n\) thành phố và \(n - 1\) con đường giữa chúng. Có một tuyến đường duy nhất giữa hai thành phố bất kì, và khoảng cách của chúng là số lượng con đường trên tuyến đường đó.
Một công ty muốn có những văn phòng ở một số thành phố, nhưng khoảng cách giữa hai văn phòng bất kỳ phải ít nhất là \(d\). Số lượng văn phòng tối đa mà họ có thể có là bao nhiêu?
Input
-
Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(d\): số lượng thành phố và khoảng cách tối thiểu. Các thành phố được đánh số \(1, 2, \ldots, n\).
-
Sau đó, có \(n - 1\) dòng mô tả các con đường. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một con đường giữa thành phố \(a\) và \(b\).
Output
- Trước tiên, in một số nguyên \(k\): số lượng văn phòng tối đa. Sau đó, in các thành phố sẽ có văn phòng. Bạn có thể in bất kì giải pháp hợp lệ nào.
Constraints
- \(1 \leq n, d \leq 2 \cdot 10 ^ 5\)
- \(1 \leq a, b \leq n\)
Example
Input:
5 3
1 2
2 3
3 4
3 5
Output:
2
1 4
Bình luận
CSES - Creating Offices | Xây dựng văn phòng
Có \(n\) thành phố và \(n - 1\) con đường nối các thành phố này. Có một tuyến đường duy nhất giữa hai thành phố bất kì, và khoảng cách giữa hai thành phố là số con đường trên tuyến đường nối chúng.
Một công ty muốn đặt văn phòng ở một số thành phố, sao cho khoảng cách tối thiểu giữa hai văn phòng là \(d\). Họ có thể đặt tối đa bao nhiêu văn phòng?
Input
Output
Example
Test 1
Input
Output