Problem1132--「一本通 4.4 例 3」异象石

1132: 「一本通 4.4 例 3」异象石

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:Contest Hunter Round #56

在 Adera 的异时空中有一张地图。这张地图上有 NNN 个点,有 N−1N-1N1 条双向边把它们连通起来。起初地图上没有任何异象石,在接下来的 MMM 个时刻中,每个时刻会发生以下三种类型的事件之一:

  1. 地图的某个点上出现了异象石(已经出现的不会再次出现);
  2. 地图某个点上的异象石被摧毁(不会摧毁没有异象石的点);
  3. 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。

请你作为玩家回答这些问题。下图是一个例子,灰色节点表示出现了异象石,加粗的边表示被选为连通异象石的边集。

stone.png


Input

第一行有一个整数 NNN,表示点的个数;

接下来 N−1N-1N1 行每行三个整数 x,y,zx,y,zx,y,z,表示点 xxxyyy 之间有一条长度为 zzz 的双向边;

N+1N+1N+1 行有一个正整数 MMM

接下来 MMM 行每行是一个事件,事件是以下三种格式之一:

  • + x:表示点 xxx 上出现了异象石;
  • - x:表示点 xxx 上的异象石被摧毁;
  • ?:表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

Output

对于每个?事件,输出一个整数表示答案。


Sample Input

6 
1 2 1 
1 3 5 
4 1 7 
4 5 3 
6 4 2 
10 
+ 3 
+ 1 
? 
+ 6 
? 
+ 5 
? 
- 6 
- 3 
?

Sample Output

5 
14 
17 
10

HINT

对于 30%30\%30% 的数据,1≤ n,m ≤ 1031\le  n, m \le 10^31 n,m 103

对于另 20%20\%20% 的数据,地图是一条链,或者一朵菊花;

对于 100%100\%100% 的数据,1≤ n,m ≤ 105,1 ≤ x,y ≤ n,x ̸= y,1 ≤ z ≤ 1091\le n, m \le 10^5, 1 \le x, y \le n, x \not = y, 1 \le z \le 10^91 n,m 105,1 x,y n,x ̸= y,1 z 109


Source/Category


Submit Status