Dynamic Programming Optimization with Convex Hull Trick
Rose- a car manufacturer finds herself as the mayor of TreeTop. The city of TreeTop is in the form of a tree with N nodes and N-1 roads joining them. For each pair of nodes u and v that are connected, the distance between them is 1 unit, however it takes c(u,v) litres of petrol to cross it (weird, isn’t it?). Each node in TreeTop has a petrol pump in which one can fill the tank of their car to the fullest. The fact that there is a pump in every node means that the tank of the car only needs to have that c(u, v) litres of petrol to cross the edge u-v.
Rose also has K dollars. She has to decide a certain capacity for the tank of the car. Given a certain capacity for the tank, results in certain roads not being crossed (for example. if the tank’s capacity is 6 litres and c(u,v) is 10 then the car can’t go from u to v or vice versa). Of Course, when some roads can’t be crossed, TreeTop decomposes into a forest (number of disjoint trees). For each tree in the forest, Rose has to assign some node in that tree as a centre. The cost of assigning a particular node as a centre is the sum of the distances of all nodes in that tree from the centre. Rose has to ensure that the cost of setting up centres in all the trees in the forest is less than or equal to K dollars.
Rose wants to choose the maximum capacity of the petrol tank so that the cost of setting up centres is not more than K. Also, the maximum capacity that the car can have is 109 litres. You have to output this maximum capacity.
Input
The first line contains 2 integers- N the number of nodes in TreeTop and K, the amount of money in dollars that Rose has.
The next N-1 lines are of the form : u v c(u, v) - denoting there is an edge between u and v of length 1 and takes c(u, v) litres of petrol to cross.
Output
Print a single integer - the maximum capacity of the car’s tank.
Constraints
1 <= N <= 105
1 <= u, v <= N
1 <= K <= 1015
1 <=c (u, v) <= 109
It is guaranteed that the graph in the input is a tree, without multiple edges or self-loops.
