This time you should help a team of researchers on an island in the Pacific Ocean. They research the culture of the ancient tribes that used to inhabit the island many years ago.
Overall they've dug out n villages. Some pairs of villages were connected by roads. People could go on the roads in both directions. Overall there were exactly n - 1 roads, and from any village one could get to any other one.
The tribes were not peaceful and they had many wars. As a result of the wars, some villages were destroyed completely. During more peaceful years some of the villages were restored.
At each moment of time people used only those roads that belonged to some shortest way between two villages that existed at the given moment. In other words, people used the minimum subset of roads in such a way, that it was possible to get from any existing village to any other existing one. Note that throughout the island's whole history, there existed exactly n - 1 roads that have been found by the researchers. There never were any other roads.
The researchers think that observing the total sum of used roads’ lengths at different moments of time can help to better understand the tribes' culture and answer several historical questions.
You will be given the full history of the tribes' existence. Your task is to determine the total length of used roads at some moments of time.
The first line contains an integer n (1 ≤ n ≤ 105) — the number of villages. The next n - 1 lines describe the roads. The i-th of these lines contains three integers ai, bi and ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 109, 1 ≤ i < n) — the numbers of villages that are connected by the i-th road and the road's length. The numbers in the lines are separated by a space.
The next line contains an integer q (1 ≤ q ≤ 105) — the number of queries. Then follow q queries, one per line, ordered by time. Each query belongs to one of three types:
It is guaranteed that the queries do not contradict each other, that is, there won't be queries to destroy non-existing villages or restore the already existing ones. It is guaranteed that we have at least one query of type "?". It is also guaranteed that one can get from any village to any other one by the given roads.
At the initial moment of time no village is considered to exist.
For each query of type "?" print the total length of used roads on a single line. You should print the answers to the queries in the order, in which they are given in the input.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.
6
1 2 1
1 3 5
4 1 7
4 5 3
6 4 2
10
+ 3
+ 1
?
+ 6
?
+ 5
?
- 6
- 3
?
5
14
17
10
| Croc Champ 2012 - Round 2 |
|---|
| Finished |
