题目描述

原题来自：Contest Hunter Round #56 在 Adera 的异时空中有一张地图。这张地图上有 $N$ 个点，有 $N-1$ 条双向边把它们连通起来。起初地图上没有任何异象石，在接下来的 $M$ 个时刻中，每个时刻会发生以下三种类型的事件之一： 地图的某个点上出现了异象石（已经出现的不会再次出现）； 地图某个点上的异象石被摧毁（不会摧毁没有异象石的点）； 向玩家询问使所有异象石所在的点连通的边集的总长度最小是多少。 请你作为玩家回答这些问题。下图是一个例子，灰色节点表示出现了异象石，加粗的边表示被选为连通异象石的边集。

输入

第一行有一个整数 $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

提示

数据范围与提示： 对于 30% 的数据，$1≤ n,m ≤ 10^3$ ； 对于另 20% 的数据，地图是一条链，或者一朵菊花； 对于 100% 的数据，$1≤ n,m ≤ 10^5 ,1 ≤ x,y ≤ n, x ≠  y,1 ≤ z ≤ 10^9$ 。

评测数据说明

本题使用经输入域与独立答案完整核验的第三方公开训练数据，并补充自编边界及公开样例，共10个测试点，非原站或官方原始数据。总分100分。公开训练数据来自HEEKDragonOne/ACM固定提交，逐点来源与SHA256保存在教师复核材料。