Sonya and Ice Cream
Contest: Codeforces Round 495 (Div. 2)
Difficulty rating: 2400
Tags: binary search, data structures, dp, greedy, shortest paths, trees

Sonya likes ice cream very much. She eats it even during programming competitions. That is why the girl decided that she wants to open her own ice cream shops.

Sonya lives in a city with $$$n$$$ junctions and $$$n-1$$$ streets between them. All streets are two-way and connect two junctions. It is possible to travel from any junction to any other using one or more streets. City Hall allows opening shops only on junctions. The girl cannot open shops in the middle of streets.

Sonya has exactly $$$k$$$ friends whom she can trust. If she opens a shop, one of her friends has to work there and not to allow anybody to eat an ice cream not paying for it. Since Sonya does not want to skip an important competition, she will not work in shops personally.

Sonya wants all her ice cream shops to form a simple path of the length $$$r$$$ ($$$1 \le r \le k$$$), i.e. to be located in different junctions $$$f_1, f_2, \dots, f_r$$$ and there is street between $$$f_i$$$ and $$$f_{i+1}$$$ for each $$$i$$$ from $$$1$$$ to $$$r-1$$$.

The girl takes care of potential buyers, so she also wants to minimize the maximum distance between the junctions to the nearest ice cream shop. The distance between two junctions $$$a$$$ and $$$b$$$ is equal to the sum of all the street lengths that you need to pass to get from the junction $$$a$$$ to the junction $$$b$$$. So Sonya wants to minimize

$$$$$$\max_{a} \min_{1 \le i \le r} d_{a,f_i}$$$$$$

where $$$a$$$ takes a value of all possible $$$n$$$ junctions, $$$f_i$$$ — the junction where the $$$i$$$-th Sonya's shop is located, and $$$d_{x,y}$$$ — the distance between the junctions $$$x$$$ and $$$y$$$.

Sonya is not sure that she can find the optimal shops locations, that is why she is asking you to help her to open not more than $$$k$$$ shops that will form a simple path and the maximum distance between any junction and the nearest shop would be minimal.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1\leq k\leq n\leq 10^5$$$) — the number of junctions and friends respectively.

Each of the next $$$n-1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$d_i$$$ ($$$1\leq u_i, v_i\leq n$$$, $$$v_i\neq u_i$$$, $$$1\leq d\leq 10^4$$$) — junctions that are connected by a street and the length of this street. It is guaranteed that each pair of junctions is connected by at most one street. It is guaranteed that you can get from any junctions to any other.

Output format:
Print one number — the minimal possible maximum distance that you need to pass to get from any junction to the nearest ice cream shop. Sonya's shops must form a simple path and the number of shops must be at most $$$k$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, you can choose the path 2-4, so the answer will be 4.

The first example.

In the second example, you can choose the path 4-1-2, so the answer will be 7.

The second example.

Example input:
6 2
1 2 3
2 3 4
4 5 2
4 6 3
2 4 6

Example output:
4

Example input:
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

Example output:
7

Editorial:
The editorial for the main solution with centroid decomposition will be published later.
Another Solution (without really formal proof)
It is possible to show, that if we have all weights equal to $$$1$$$, then optimal answer is always a middle part of diameter of right length.
However, weights are arbitrary. Then we need to select a "weighted" middle part.
We can do it in a following way: set two pointers — one to the diameter beginning, and one to the end.
And while the number of vertices is greater $$$k$$$ we move the pointer, which has moved less from it's end.
However, in fact, sometimes we need to look at the neighboring $$$\pm 1$$$ possible subpaths —- for example if the last step was the same distance, then the optimal move depends on where the edge was longer.
This way we need to count answer for $$$\le 3$$$ paths. To count the answer for path we can run few dfs's, each of them will cover only part of graph, which hangs on related vertex of the path.
Complexity is $$$\mathcal{O}(n)$$$.
The sketch of the proof is something like this:
Examine the diameter. Notice, that the answer should contain it's middle point (vertex, which is most close to $$$1/2$$$) because the answer would be greater than the largest half of this diameter otherwise.
From this we already bounded our answer, but we need more.
Then we want to start to grow the way to the ends of the diameter, so that at least from the end of the diameter of the distance was small.
Not the fact that this will be enough (for example, if there are several diameters), but it is necessary.
Two pointers are needed because growing in two directions may be necessary unevenly.