Problem Description

Adera is a puzzle game in the Microsoft Store.

The anomalous stone is a guide that allows entry into the alternate space-time in Adera, and there is a map in this alternate space-time.

On this map, there are $N$ nodes, and $N-1$ undirected edges connecting them.

At the beginning, there are no anomalous stones on the map. During the next $M$ moments, at each moment, one of the following three types of events will occur:

1. An anomalous stone appears at some node on the map (a node that already has one will not get another).
2. The anomalous stone at some node on the map is destroyed (a node without one will not be destroyed).
3. The player is asked: what is the minimum total length of the set of edges needed to make all nodes that currently have anomalous stones connected.

Please answer these queries as the player.

Input Format

The first line contains an integer $N$, representing the number of nodes.

The next $N-1$ lines each contain three integers $x, y, z$, indicating that there is an undirected edge of length $z$ between node $x$ and node $y$.

Line $N+1$ contains a positive integer $M$.

The next $M$ lines each describe an event in one of the following formats:

• + x means an anomalous stone appears at node $x$.
• - x means the anomalous stone at node $x$ is destroyed.
• ? means a query asking for the minimum total length of the set of edges needed to connect all nodes that currently have anomalous stones.

Output Format

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

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

Hint

Constraints: $1 \le N, M \le 10^5$, $1 \le x, y \le N$, $x \neq y$, $1 \le z \le 10^9$.

Translated by ChatGPT 5