18947번 - Tree Hull 다국어

문제

You are given an edge-weighted tree.

Consider a set $A$ which is a subset of vertices of the tree. Initially, $A$ is empty, and we have to process queries which ask to add a vertex to $A$ or remove a vertex from $A$.

After each query, find the weight of the minimum subtree containing all vertices from $A$. We define the weight of the subtree as the sum of weights of its edges.

입력

The first line of input contains an integer $n$: the size of the tree (1ドル \le n \le 3 \cdot 10^{5}$).

The next $n-1$ lines describe edges of the tree. Each edge is described as "$u$ $v$ $w$": its endpoints and weight (1ドル \le u, v \le n,ドル $u \ne v,ドル 0ドル \le w \le 10^{9}$). It is guaranteed that the given edges form a tree.

The following line contains an integer $q$: the number of queries (1ドル \le q \le 3 \cdot 10^{5}$).

The next $q$ lines contain queries. Each query is given as "$t$ $v$", where $t$ is either "+" (add vertex to $A$) or "-" (remove vertex from $A$), and $v$ is the number of the vertex (1ドル \le v \le n$). It is guaranteed that you are never asked to add a vertex which is already in $A,ドル or to remove a vertex which is not currently in $A$.

출력

Print $q$ numbers: the weight of the smallest subtree containing all vertices from $A$ after each query. In case $A$ is empty, print a 0ドル$.

제한

힌트