CF176E Archaeology

这一次，你需要帮助一支在太平洋上某座岛屿上的研究团队。他们正在研究多年前曾居住在该岛上的古代部落的文化。 总共他们挖掘出了 $n$ 个村庄。一些成对的村庄之间由道路相连。道路是双向的。总共有恰好 $n-1$ 条道路，并且从任意一个村庄都可以到达其他任何村庄。 这些部落并不和平，他们之间爆发了许多战争。战争的结果是一些村庄被完全摧毁。在较为和平的年代，一些村庄又被重建。 在每一时刻，人们只使用那些属于当时所有存在村庄之间的最短路径上的道路。换句话说，人们总是使用最少的道路集合，使得任意两个当时存在的村庄之间都可以互相到达。请注意，在整个岛屿历史当中，被研究者发现的道路始终恰好只有 $n-1$ 条，道路数量没有变化，也没有其他道路存在。 研究人员认为，观察不同历史时期所使用的道路总长度，有助于更好地理解这些部落的文化，并解答一些历史问题。 你将被给出部落历史的完整变化过程。你的任务是在某些时刻确定被实际使用的道路的总长度。

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$），表示村庄的数量。 接下来 $n-1$ 行描述道路，第 $i$ 行包含三个整数 $a_{i}$、$b_{i}$、$c_{i}$（$1 \leq a_{i}, b_{i} \leq n$，$a_{i} \neq b_{i}$，$1 \leq c_{i} \leq 10^{9}$，$1 \leq i < n$），表示第 $i$ 条道路连接着村庄 $a_{i}$ 和 $b_{i}$，其长度为 $c_{i}$。每行中的数用一个空格隔开。 下一行包含一个整数 $q$（$1 \leq q \leq 10^{5}$），表示查询的数量。 接下来 $q$ 行，每行一个查询，按时间顺序给出。查询类型有三种： - `+ x` —— 村庄编号 $x$ 被重建（$1 \leq x \leq n$）。 - `- x` —— 村庄编号 $x$ 被摧毁（$1 \leq x \leq n$）。 - `?` —— 考古学家想知道当前被实际使用的道路的总长度。 保证所有查询不会互相矛盾，即不会摧毁已经不存在的村庄，也不会重建已经存在的村庄。保证至少有一个 `?` 查询。并且保证最初没有任何村庄存在。

对于每个 `?` 类型的查询，按出现顺序各输出一行，内容为当前被实际使用的道路的总长度。 请不要在 C++ 中用 %lld 读写 64 位整数。推荐使用 cin、cout 流或者 %I64d。

由 ChatGPT 5 翻译