Hide and seek

Time Limit: 8 Seconds
Memory Limit: 65536 KB

*Flandre Scarlet* loves her elder sister *Remilia Scarlet*, of course, *Remilia* loves *Flandre*, too. But because of *Flandre*'s unstable personality and incredible destructive power, *Remilia* has ordered *Flandre* not to leave *Scarlet Devil Mansion* for nearly 500 years. The life of *Flandre* is so boring that it's no surprising that she did some unimaginable things. To solve this problem, *Remilia* decides to play a famous game in *Scarlet Devil Mansion* with *Flandre*: Hide and seek.

Now it's *Remilia*'s turn to hide and *Flandre* must to find her sister. To reduce the difficulty of the game, *Remilia* have told *Flandre* that there are `N` hiding places. By the way, there are exactly `N-1` roads that connect all places, and each road has a length `L`. The roads are all bidirectional.

Although *Flandre* doesn't tell her sister, she has a secret ability that she can build a new road between two places with a length `X`. But it's no obvious that what's the best plan to build the road, so *Flandre* asked you to calculate the sum of the decreasing distances from all places (including `A` and `B`) to `A` and `B` if building a road between `A` and `B` with length `X`, and then she can know how to find her sister as soon as possible.

#### Input

There are multiple test cases. For each test case:

The first line contains an integer `N` (1 <= `N` <= 50000) indicates the `N` hiding places in *Scarlet Devil Mansion*. Then followed by `N-1` lines, each line contains three integers: `X`_{i}, `Y`_{i} and `L`_{i} (1 <= `X`_{i},`Y`_{i} <= `N`, 0 <= `L`_{i} <= 10000), which means there's a road between `X`_{i} and `Y`_{i}, and the length is `L`_{i}.

Next, there is one line contains an integer `M` (0 <= `M` <= 100000) indicates the `M` queries that *Flandre* asks. Then followed by `M` lines, each line contains three integers: `X`_{i}, `Y`_{i} and `L`_{i} (1 <= `X`_{i},`Y`_{i} <= `N`, 0 <= `L`_{i} <= 10000), which means *Flandre* tries to build a new road between place `X`_{i} and `Y`_{i}, and the length is `L`_{i}.

#### Output

For each test case, output `M` integers corresponding to the *Flandre*'s queries.

#### Sample Input

5
1 2 3
1 3 2
2 4 1
3 5 3
2
4 5 1
1 2 2

#### Sample Output

24
5

#### Hint

In the first sample, if *Flandre* builds a road between 4 and 5 and the length is 1, the changes are: [4,5] 9->1 [2,5] 8->2 [3,4] 6->4 [5,4] 9->1 ([from, to] original distance -> nowdistance), so the answer is 8+6+2+8=24.

Author:

**DAI, Longao**
Submit
Status