#lCAlydlt60x6306. 异象石
异象石
好的,这是整理好的题面,不含解题思路,只包含样例解释。
题目描述
Adera 是一款解谜游戏。
异象石是进入异时空的引导物,在异时空有一张地图。
地图上有 个点,由 条双向边连通(形成一棵树)。
起初没有任何异象石。
在接下来的 个时刻中,每个时刻会发生以下三种类型的事件之一:
+ 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
样例解释
树的结构(边权):
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
按事件顺序分析:
-
+ 3:点 3 出现异象石。集合 {3} -
+ 1:点 1 出现异象石。集合 {3, 1} -
?:当前集合 {3, 1},两点间路径 1-3 长度 5,最小连通边集就是这条边,长度 5。输出 5。 -
+ 6:点 6 出现异象石。集合 {3, 1, 6} -
?:集合 {3, 1, 6},最小连通子图包含路径 1-3(5),1-4(7),4-6(2)。
总长 = 5 + 7 + 2 = 14。输出 14。 -
+ 5:点 5 出现异象石。集合 {3, 1, 6, 5} -
?:集合 {3, 1, 6, 5},最小连通子图包含路径 1-3(5),1-4(7),4-6(2),4-5(3)。
总长 = 5 + 7 + 2 + 3 = 17。输出 17。 -
- 6:点 6 异象石消失。集合 {3, 1, 5} -
- 3:点 3 异象石消失。集合 {1, 5} -
?:集合 {1, 5},两点间路径 1-4-5 长度 7+3=10。输出 10。
最终输出序列:5 14 17 10。