D. Хөгжилтэйгээр дэд модыг сонго

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$n$ ширхэг оройтой мод байжээ. Оройнууд нь $1$-ээс $n$ хүртэл дугаарлагдсан.

[$l, r$] интервалын уртыг $r- l + 1$ гэж үзье.. Энэ модны дэд модны оноо нь [$l,r$] интервал буюу $l, l+1, ... , r$ дугаарлагдсан оройтой моднуудын хамгийн уртаар тодорхойлогдно.

$к$ хэмжээтэй модны хувьд түүний бүх дэд модны хамгийн их оноо нь түүний дэд модднуудын хамгийн их оноог буцаана. Энэхүү мод нь өлгөгдөөгүй ба дэд мод нь дурын холбогдсон дэд граф байна.

Оролт

Эхний мөрөнд $n$, $k$ ($1 ≤ k ≤ n ≤ 10^5$) хоёр тоо байна. Дараагийн $n-1$ ширхэг мөр бүр холбогдсон хоёр орой болох $a_i$ ба $b_i$-г ($1 ≤ a_i, b_i ≤ n$, $a_i ≠ b_i$) агуулна. Энэ граф мод болох нь баталгаатай.

Гаралт

Хамгийн их оноо болох $1$ тоог хэвлэ.

Орчуулсан: Баттулга

Жишээ тэстүүд

Оролт
10 6
4 10
10 6
2 9
9 6
8 5
7 1
4 7
7 3
1 8
Гаралт
3
Оролт
16 7
13 11
12 11
2 14
8 6
9 15
16 11
5 14
6 15
4 3
11 15
15 14
10 1
3 14
14 7
1 7
Гаралт
6

Тэмдэглэл

For the first case, there is some subtree whose size is at most $6$, including $3$ consecutive numbers of vertices. For example, the subtree that consists of ${1, 3, 4, 5, 7, 8}$ or of ${1, 4, 6, 7, 8, 10}$ includes $3$ consecutive numbers of vertices. But there is no subtree whose size is at most $6$, which includes $4$ or more consecutive numbers of vertices.

Сэтгэгдлүүдийг ачааллаж байна...