시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 256 MB | 23 | 9 | 9 | 39.130% |
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$.
5 1 2 1 2 3 10 3 4 100 3 5 1000 8 + 2 + 5 + 4 - 5 + 1 - 4 - 2 - 1
0 1010 1110 110 111 1 0 0