Codeforces Round 495 (Div. 2) |
---|
Закончено |
Соня очень любит мороженое. Она ест его даже во время соревнований по программированию. Поэтому, девочка решила, что хочет открыть свои собственные магазины мороженого.
Соня живет в городе, в котором всего $$$n$$$ перекрестков и $$$n-1$$$ улиц. Все улицы — двусторонние и соединяют пары перекрестков. С любого перекрестка можно попасть в любой другой перекресток в городе, пройдя по одной или более улиц. Мэрия позволяет открывать магазины только на перекрестках, девочка не может открывать магазины посреди улиц, между перекрестками.
У Сони есть ровно $$$k$$$ друзей, которым она доверяет. Если она откроет магазин, один с её друзей должен там работать и смотреть, чтобы никто не ел мороженое не заплатив. Поскольку Соня не хочет пропускать важные соревнования по программированию, непосредственно в магазинах она работать не будет.
Соня хочет, чтобы все её магазины мороженого образовали простой путь длины $$$r$$$ ($$$1 \le r \le k$$$), то есть были расположены в различных перекрёстках $$$f_1, f_2, \dots, f_r$$$ и существовала улица между $$$f_i$$$ и $$$f_{i+1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$r-1$$$.
Девочка заботится о потенциальных покупателях, поэтому, она также хочет минимизировать максимальное расстояние от перекрестков до ближайшего магазина мороженого. Расстояние между двумя перекрестками $$$a$$$ и $$$b$$$ равно сумме длин всех улиц, которые нужно пройти, чтобы попасть с перекрестка $$$a$$$ на перекресток $$$b$$$. Таким образом, девочка хочет минимизировать
$$$$$$\max_{a} \min_{1 \le i \le r} d_{a,f_i}$$$$$$,
где $$$a$$$ принимает значение всевозможных $$$n$$$ перекрёстков, $$$f_i$$$ — перекресток с $$$i$$$-м магазином Сони, а $$$d_{x,y}$$$ — расстояние между перекрестками $$$x$$$ и $$$y$$$.
Соня неуверенна, что сможет найти оптимальные местоположения магазинов, поэтому, просит вас помочь ей открыть не более $$$k$$$ магазинов, которые образуют простой путь, и максимальное расстояние от произвольного перекрестка города до ближайшего магазина минимально.
Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1\leq k\leq n\leq 10^5$$$) — количество перекрестков и друзей соответственно.
Каждая из следующих $$$n-1$$$ строк содержит три целых числа $$$u_i$$$, $$$v_i$$$ и $$$d_i$$$ ($$$1\leq u_i, v_i\leq n$$$, $$$v_i\neq u_i$$$, $$$1\leq d\leq 10^4$$$) — перекрестки, которые соединяет улица и длина этой улицы. Гарантируется, что между любой парой перекрестков не более одной улицы. Гарантируется, что можно доехать из любого перекрестка в любой другой, двигаясь только по улицам.
Выведите одно число — минимальное максимальное расстояние, которое нужно будет пройти, чтобы попасть с любого перекрестка до ближайшего магазина мороженого. Магазины Сони должны располагаться вдоль произвольного простого пути из перекрестков длины не более $$$k$$$.
6 2
1 2 3
2 3 4
4 5 2
4 6 3
2 4 6
4
10 3
1 2 5
5 7 2
3 2 6
10 6 3
3 8 1
6 4 2
4 1 6
6 9 4
5 2 5
7
В первом примере можно выбрать путь 2-4, тогда ответ будет 4.
Во втором примере можно выбрать путь 4-1-2, тогда ответ будет 7.
Название |
---|