nodes and
edges). Bob is currently on the ground, marked node
. Every day,
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?
Input Specification
The first line contains , the number of nodes, and
, the number of days.
The next lines contain
,
, and
, marking a branch between
and
of length
.
The next lines contain
and
, the location of the 2 bananas that day.
Output Specification
Output the minimum total distance the monkey must travel.
Constraints
For all subtasks:
Subtask 1 [10%]
Subtask 2 [20%]
Sample Input
5 2
1 2 4
2 4 3
4 3 1
5 4 1
5 3
2 5
Sample Output
14
On the first day, Bob starts at node and travels to node
and then node
to eat the bananas.
On the second day, Bob is already at node and eats the banana before travelling to node
.
Comments