题目描述

在 Adera 的异时空中有一张地图。这张地图上有 $N$ 个点，有 $N-1$ 条双向边把它们连通起来，形成一棵树，每条边有一个长度。

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

1. +x：地图的某个点 $x$ 上出现了异象石（已经出现的不会再次出现）；
2. -x：地图某个点 $x$ 上的异象石被摧毁（不会摧毁没有异象石的点）；
3. ?：询问使所有异象石所在的点连通的边集的总长度最小是多少。

你需要对每个 ? 事件输出答案。

输入格式

第一行有一个整数 $N$，表示点的个数；

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

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

接下来 $M$ 行，每行是一个事件，事件是以下三种格式之一：

• +x：表示点 $x$ 上出现了异象石；
• -x：表示点 $x$ 上的异象石被摧毁；
• ?：表示询问使当前所有异象石所在的点连通所需的边集的总长度最小是多少。

输出格式

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

样例

输入样例 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
      / | \
     /  |  \
    2(1)3(5)4(7)
            / \
          5(3)6(2)

• 第一次出现异象石：节点 $3$。
• 第二次出现异象石：节点 $1$。
• 第一次询问：只有节点 $1$ 和 $3$，连接它们的最短路径是 $1 \to 3$，长度 $5$。
• 第三次出现异象石：节点 $6$。
• 第二次询问：节点 $1,3,6$。最小连通边集是 $1 \to 3$ ($5$) 和 $4 \to 6$ ($2$)，但 $1$ 到 $4$ 的边 ($7$) 也必须加上，因为 $1,3$ 在一边，$6$ 在另一边。实际上连接这三个点的最小生成树就是它们之间的路径并，可以用虚树的思想得到：所有异象石节点按 DFS 序排序后相邻两点的距离和的一半（加上首尾距离和的一半）。具体计算：
  • 按 DFS 序排序：假设 DFS 序为 $1,3,6$（实际按树的结构），相邻距离：$dist(1,3)=5$, $dist(3,6)=dist(3,1)+dist(1,4)+dist(4,6)=5+7+2=14$，总和 $5+14=19$，但实际最小边集长度应为 $(5+14+?)/2$ 需要正确计算，这里先不展开，结果是 $14$。
• 第四次出现异象石：节点 $5$。
• 第三次询问：节点 $1,3,5,6$，结果 $17$。
• 摧毁节点 $6$ 的异象石。
• 摧毁节点 $3$ 的异象石。
• 第四次询问：剩下节点 $1,5$，连接路径 $1\to4\to5$，长度 $7+3=10$。

数据范围

• $1 \le N, M \le 10^5$
• $1 \le x, y \le N, x \ne y$
• $1 \le z \le 10^9$

时间限制：1000 ms
内存限制：524288 KB

提示

本题的关键结论（需要掌握）：

设当前所有异象石节点按 DFS 序排序后为 $a_1, a_2, \dots, a_k$，那么连接这些点的最小边集总长度为：

其中 $a_{k+1} = a_1$，$dist(u,v)$ 表示树上两点间路径长度。

这个式子的意义是：按 DFS 序排序后，相邻节点（包括首尾）在树上的路径并起来正好覆盖了所需的最小连通边集每条边两次。

因此，我们需要维护一个按 DFS 序排序的异象石节点集合，支持插入、删除，并动态维护相邻节点距离和（包括首尾相邻）。查询时输出这个和的一半即可。

实现步骤：

1. 预处理树的 DFS 序、深度、距离根节点的距离 $dis[i]$，以及倍增 LCA 所需信息。
2. 用平衡树（如 set）按 DFS 序存储当前异象石节点。
3. 插入节点 $x$ 时，在 set 中找到它的前驱和后继，更新距离和：
   • 原来前驱和后继之间的距离从总和中减去；
   • 加上 $dist(前驱, x)$ 和 $dist(x, 后继)$。
4. 删除节点 $x$ 时，类似地更新距离和。
5. 查询时，总和除以 $2$ 输出。

注意：set 为空时查询结果为 $0$；只有一个节点时，总和为 $2 \times dist(x,x)=0$，答案 $0$。

时间复杂度：每个操作 $O(\log n)$（set 操作和 LCA 查询）。