VPEX P4 - Etopika


Submit solution

Points: 12 (partial)
Time limit: 3.0s
Java 11 4.0s
Memory limit: 128M

Author:
Problem types

Bobliu the monkey is living on a tree. The tree can be modelled as a tree (a connected graph with 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?

Input

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

Output the minimum total distance the monkey must travel.

Subtasks

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

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 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.


Comments

There are no comments at the moment.