Lightning Energy Report#3329
The city of Thunder has many houses, and they are powered by lightning. Two houses may be interconnected by a wire. The wires connect the houses such that there is exactly one path from one house to any other house in the city. Each house has a large battery that can store infinite electrical energy.
Every day, several lightnings strike several houses. These lightnings are very unusual: when lightning strikes, it strikes two houses simultaneously—one house () with a red lightning bolt, and the other house () with a blue lightning bolt. After the strikes, every house along the path from to (inclusive) will receive a certain amount of electrical energy, which is then added to the house's battery.
The mayor of Thunder city wants a report on the stored electrical energy for every house at the end of the month, and the owner of each house has to pay taxes for that. To prevent the owners from reporting invalid energy stored in their house batteries (because they want to pay less tax), you are asked to produce a correct report based on the observed lightnings of the current month. At the beginning of the month, the energy reading on the battery of each house is .
The first line of input contains an integer (T \leq 10), the number of cases. Each case begins with an integer (2 \leq N \leq 50\,000), the number of houses in Thunder city. The next N - 1 lines contain the wire connections, where each line consists of two integers and , which means house is connected with house . The house numbers range from to N - 1. The next line will contain a number (1 \leq Q \leq 50\,000), which denotes the number of observed lightning strikes. The next lines describe the unusual lightnings that happened during the month. Each line will consist of three integers , , , which means a red lightning strikes house and a blue lightning strikes house , and the power transferred is (at most ) based on the reading of a special lightning instrument.
For each case, output Case #: (without quotes), where is the case number, followed by lines, where each line is the electrical energy reading on the battery of each house from house to house N-1 at the end of the month.
1-nji mysal