#lCAlydlt60x6306. 异象石

异象石

好的,这是整理好的题面,不含解题思路,只包含样例解释。


题目描述

Adera 是一款解谜游戏。
异象石是进入异时空的引导物,在异时空有一张地图。

地图上有 NN 个点,由 N1N-1 条双向边连通(形成一棵树)。
起初没有任何异象石。

在接下来的 MM 个时刻中,每个时刻会发生以下三种类型的事件之一:

  1. + x:点 xx 上出现了异象石(不会重复出现在已有异象石的点)。
  2. - x:点 xx 上的异象石被摧毁(不会摧毁没有异象石的点)。
  3. ? :询问:使当前所有异象石所在的点连通的边集的总长度最小是多少

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


输入格式

第一行一个整数 NN,表示点数。
接下来 N1N-1 行,每行三个整数 x,y,zx,y,z,表示点 xxyy 之间有一条长度为 zz 的双向边。
N+1N+1 行一个正整数 MM,表示事件数。
接下来 MM 行,每行一个事件,格式为 + x- x?

输出格式

对于每个 ? 事件,输出一行一个整数,表示最小连通边集的总长度。

数据范围

  • 1N,M1051 \le N,M \le 10^5
  • 1x,yN,xy1 \le x,y \le N, x \ne y
  • 1z1091 \le z \le 10^9

输入样例

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

样例解释

树的结构(边权):

        2(1)
         |
1(5)     1
   |     |
   3     4(7)
         / \
       5(3) 6(2)

实际上树的结构如下(括号里是边权): 1—2 长度 1
1—3 长度 5
1—4 长度 7
4—5 长度 3
4—6 长度 2

更清晰的表示:

        3
        | 5
   2 -- 1 -- 4 -- 5
  1        7    3
            \
             6
             2

按事件顺序分析

  1. + 3:点 3 出现异象石。集合 {3}

  2. + 1:点 1 出现异象石。集合 {3, 1}

  3. ?:当前集合 {3, 1},两点间路径 1-3 长度 5,最小连通边集就是这条边,长度 5。输出 5。

  4. + 6:点 6 出现异象石。集合 {3, 1, 6}

  5. ?:集合 {3, 1, 6},最小连通子图包含路径 1-3(5),1-4(7),4-6(2)。
    总长 = 5 + 7 + 2 = 14。输出 14。

  6. + 5:点 5 出现异象石。集合 {3, 1, 6, 5}

  7. ?:集合 {3, 1, 6, 5},最小连通子图包含路径 1-3(5),1-4(7),4-6(2),4-5(3)。
    总长 = 5 + 7 + 2 + 3 = 17。输出 17。

  8. - 6:点 6 异象石消失。集合 {3, 1, 5}

  9. - 3:点 3 异象石消失。集合 {1, 5}

  10. ?:集合 {1, 5},两点间路径 1-4-5 长度 7+3=10。输出 10。


最终输出序列5 14 17 10