Trams of Berlin P51603


Statement
 

pdf   zip

html

Baq is living in Berlin, a city really well connected thanks to its great public transport service. In particular, it has quite a vast tram network, with a peculiar characteristic: between any two tram stops, there is exactly one route that connects them.

Baq has made a lot of friends in the city, and they are going to meet him soon, each on a different day. For each meeting i, let xi and yi be the tram stops where Baq and his i-th friend plan to be before the meeting, respectively. They will meet halfway, that is, at the stop that falls closer to the middle point following the route that connects xi and yi. In case of a tie, they will choose the tram stop closer to Baq. Can you efficiently compute the total distance travelled by each of Baq’s friends?

Input

Input consists of several cases. Every case begins with the number of tram stops n. Follow n−1 triples x y ℓ describing a street of length ℓ connecting x and y. Follow n queries xi yi. Assume 2 ≤ n ≤ 105, that tram stops are numbered starting at 0, 1 ≤ ℓ ≤ 109, that the given streets form a tree, and that the queries are all different.

Output

For each case, print the total distance of the travel of every Baq’s friend. Print a line with 10 dashes at the end of each case.

Public test cases

  • Input

    2
1 0 100
0 1
1 1

7
0 1 999999999
2 1 1000000000
6 3 1
4 3 1000000000
5 4 999999998
0 3 1000000000
1 0
0 2
2 0
3 6
2 5
5 2
2 6

    Output

    100
0
----------
999999999
1000000000
999999999
1
2999999998
1999999999
1000000001
----------
    • Information
    Author
    Víctor Martín
    Language
    English
    Official solutions
    C++
    User solutions
    C++