ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Petrozavodsk Summer 2018. t.me/umnik_team Contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Tree Hull

Time limit: 5.0 second
Memory limit: 256 MB
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.

Input

The first line of input contains an integer n: the size of the tree (1 ≤ n ≤ 3 · 105).
The next n−1 lines describe edges of the tree. Each edge is described as “u v w”: its endpoints and weight (1 ≤ u, vn, uv, 0 ≤ w ≤ 109). It is guaranteed that the given edges form a tree.
The following line contains an integer q: the number of queries (1 ≤ q ≤ 3 · 105).
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 ≤ vn). 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.

Output

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.

Sample

inputoutput
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
Problem Author: Alexey Danilyuk
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest
To submit the solution for this problem go to the Problem set: 2119. Tree Hull