问题 AL: 异象石
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:4
解决:1
题目描述
在Adera的异时空中有一张地图。这张地图上有N个点,有N-1条双向边把它们连通起来。起初地图上没有任何异象石,在接下来的M个时刻中,每个时刻会发生以下三种类型的事件之一:
- 地图的某个点上出现了异象石(已经出现的不会再次出现);
- 地图某个点上的异象石被摧毁(不会摧毁没有异象石的点);
- 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。
请你作为玩家回答这些问题。下图是一个例子,灰色节点表示出现了异象石,加粗的边表示被选为连通异象石的边集。
输入
第一行有一个整数N,表示点的个数;
接下来N-1行每行三个整数x,y,z,表示点x和y之间有一条长度为z的双向边;
第N+1行有一个正整数M;
接下来M行每行是一个事件,事件是以下三种格式之一:
+x:表示点x上出现了异象石;
-x:表示点x上的异象石被摧毁;
?:表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。
接下来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
提示
对于30%的数据,1≤n,m≤103;
对于另20%的数据,地图是一条链,或者一朵菊花;
对于100%的数据,1≤n,m≤105,1≤x,y≤n,x≠y,1≤z≤109。
对于另20%的数据,地图是一条链,或者一朵菊花;
对于100%的数据,1≤n,m≤105,1≤x,y≤n,x≠y,1≤z≤109。