~N~ nodes and ~N-1~ edges). Bob is currently on the ground, marked node ~1~. Every day, ~2~ new nodes (not always distinct) grow a banana, and Bob climbs from his current spot to the 2 bananas (in any order) and eats them. He then takes a nap where he is and sleeps until the next day. What is the least distance he must travel?the monkey lives on a banana tree. The tree can be modelled as a tree (a connected graph with
The first line contains ~N~, the number of nodes, and ~D~, the number of days.
The next ~N-1~ lines contain ~a~, ~b~, and ~c~, marking a branch between ~a~ and ~b~ of length ~c~.
The next ~D~ lines contain ~x~ and ~y~, the location of the 2 bananas that day.
Output the minimum total distance the monkey must travel.
For all subtasks:
~1\le a,b,x,y\le N~
~0\le c\le 1000~
~1\le N\le 10^5~
~1\le D\le 10^6~
Subtask 1 [10%]
~1\le D,N\le 10~
Subtask 2 [20%]
~1\le N\le 1000~
5 2 1 2 4 2 4 3 4 3 1 5 4 1 5 3 2 5
On the first day, Bob starts at node ~1~ and travels to node ~3~ and then node ~5~ to eat the bananas.
On the second day, Bob is already at node ~5~ and eats the banana before travelling to node ~2~.