题目 2460:
信息学奥赛一本通T1554-异象石
时间限制: 2s
内存限制: 192MB 提交: 6 解决: 5
题目描述
原题来自：Contest Hunter Round #56
在 Adera 的异时空中有一张地图。这张地图上有 N 个点，有 N−1 条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的 M 个时刻中，每个时刻会发生以下三种类型的事件之一：
地图的某个点上出现了异象石（已经出现的不会再次出现）；
地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）；
向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。
在 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 。
对于 30% 的数据，1≤ n,m ≤ 103 ；
对于另 20% 的数据，地图是一条链，或者一朵菊花；
对于 100% 的数据，1≤ n,m ≤ 105,1 ≤ x,y ≤ n,x≠ y,1 ≤ z ≤ 109 。