Description

Original Source: Contest Hunter Round #56

In the alternate dimension of Adera, there is a map. This map contains $N$ points connected by $N-1$ bidirectional edges. Initially, there are no anomaly stones on the map. Over the next $M$ moments, one of the following three types of events will occur at each moment:

1. An anomaly stone appears at a certain point on the map (points that already have an anomaly stone will not reappear);
2. An anomaly stone at a certain point on the map is destroyed (points without anomaly stones will not be destroyed);
3. The player is asked to determine the minimum total length of the edge set required to connect all points currently containing anomaly stones.

As the player, please answer these queries. The figure below is an example, where gray nodes represent points with anomaly stones, and bold edges indicate the selected edge set for connecting the anomaly stones.

Input Format

The first line contains an integer $N$, indicating the number of points;

The next $N-1$ lines each contain three integers $x, y, z$, indicating a bidirectional edge between point $x$ and $y$ with length $z$;

The $(N+1)$-th line contains a positive integer $M$;

The following $M$ lines each describe an event, which is one of the following three formats:

• + x: Indicates that an anomaly stone appears at point $x$;
• - x: Indicates that the anomaly stone at point $x$ is destroyed;
• ?: Asks for the minimum total length of the edge set required to connect all points currently containing anomaly stones.

Output Format

For each ? event, output an integer representing the answer.

Sample 1

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

Data Range and Hints

For $30\%$ of the data, $1\le n, m \le 10^3$;

For another $20\%$ of the data, the map is either a chain or a star-shaped graph;

For $100\%$ of the data, $1\le n, m \le 10^5, 1 \le x, y \le n, x \not = y, 1 \le z \le 10^9$.