시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB42201946.341%

## 문제

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$.

## 예제 입력 1

5
1 2 1
2 3 10
3 4 100
3 5 1000
8
+ 2
+ 5
+ 4
- 5
+ 1
- 4
- 2
- 1


## 예제 출력 1

0
1010
1110
110
111
1
0
0
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.6005874276161194, "perplexity": 609.623406299028}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2022-40/segments/1664030334596.27/warc/CC-MAIN-20220925193816-20220925223816-00278.warc.gz"}