#3478. 异象石 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

Adera是Microsoft应用商店中的一款解谜游戏。

异象石是进入Adera中异时空的引导物,在Adera的异时空中有一张地图。

这张地图上有N个点,有N-1条双向边把它们连通起来。

起初地图上没有任何异象石,在接下来的M个时刻中,每个时刻会发生以下三种类型的事件之一:

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

请你作为玩家回答这些问题。

输入格式

第一行有一个整数N,表示点的个数。

接下来N-1行每行三个整数x,y,z,表示点x和y之间有一条长度为z的双向边。

第N+1行有一个正整数M。

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

”+ x” 表示点x上出现了异象石

”- x” 表示点x上的异象石被摧毁

”?” 表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

输出格式

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

样例

样例输入

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

样例输出

5
14
17
10

数据范围与提示

,

,

,