该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

0x60图论（0x63 树的直径与最近公共祖先）例题7：异象石

P10930 异象石

题目描述

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$ 上的异象石被摧毁
• ? 表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

5
14
17
10

说明/提示

数据保证，$1 \le N,M \le 10^5$，$1 \le x,y \le N$，$x \neq y$，$1 \le z \le 10^9$。