ZOJ Problem Set - 3522
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.
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: Xi, Yi and Li (1 <= Xi,Yi <= N, 0 <= Li <= 10000), which means there's a road between Xi and Yi, and the length is Li.
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: Xi, Yi and Li (1 <= Xi,Yi <= N, 0 <= Li <= 10000), which means Flandre tries to build a new road between place Xi and Yi, and the length is Li.
For each test case, output M integers corresponding to the Flandre's queries.
5 1 2 3 1 3 2 2 4 1 3 5 3 2 4 5 1 1 2 2
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