10-11 класс


(Тағы да ағаштар) Төбелер саны $n$, қабырғалары екі жаққа да бағытталған ағаш берілген. Екі төбенің арасындағы арақашықтық, олардың арасындағы ең қысқа жолында жатқан қабырғалардың саны деп есептеледі. Арақашықтығы ең алыс орналасқан екі төбенің арасындағы арақашықтықты -- ағаштың диаметрі деп атайды.
Бұл есепте ең көп дегенде $k$ жою операциясын қолдану арқылы ағаштың диаметрін ықшамдау керек.
Жою операциясы -- бір төбені және оған жалғанған барлық қабырғаларды жою, сонымен қатар, төбе жойылғаннан граф байланысты болмай қалса, оны жоюға болмайды.
Кіріс деректер форматы:
Бірінші жолда $n$ және $k$ сандары ($0 \le k \le n - 1$) - төбелер саны және жоюға болатын төбелердің максималды саны.
Келесі $n-1$ жолда графтың қабырғалары берілген.
Әр жолда $u$ және $v$ сандары берілген ($1 \le u, v \le n$) - $u$ және $v$ төбелерінің арасында екі жаққа бағытталған қабырғаның бар екенін білдіреді.
Шығыс деректер форматы:
Бір сан шығарыңыз -- ағашқа ең көп дегенде $k$ жою операциясын қолдану арқылы алынған ең кіші диаметрі.
Мысалдар:
1.Мысал:
5 2
1 4
3 2
1 2
5 2
Жауап:
2
2.Мысал:
14 5
13 2
10 4
6 12
8 11
11 13
5 14
10 3
11 5
12 1
9 7
11 10
10 9
6 10
Жауап:
3
Бағалау:
Есеп 100 тесттен тұрады, әр тест 1 ұпаіға бағаланады.
Тесттердегі шектеулер:
( Askhat Zhalgasov )
посмотреть в олимпиаде

Комментарий/решение: