← 返回题目列表

Codeforces · 176/E

E. 考古学

中文机器翻译题面 查看原题

这次你应该帮助太平洋岛屿上的一组研究人员。他们研究多年前居住在岛上的古代部落的文化。

总的来说,他们已经挖出了n个村庄。一些对村庄有道路相连。人们可以在道路上双向行走。总共有 n - 1 条路,从任何一个村庄都可以到达任何另一个村庄。

各部落并不太平,经常发生战争。由于战争,一些村庄被完全摧毁。在比较和平的年代,一些村庄得到了恢复。

在每个时刻,人们只使用属于特定时刻存在的两个村庄之间的某些最短路线的道路。换句话说,人们使用最小的道路子集,使得可以从任何现有的村庄到达任何其他现有的村庄。请注意,在该岛的整个历史中,研究人员发现了 n - 1 条道路。从来没有任何其他道路。

研究人员认为,观察不同时刻使用的道路长度总和有助于更好地了解部落文化并回答一些历史问题。

您将获得部落存在的完整历史。您的任务是确定某些时刻已使用道路的总长度。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 村庄的数量。接下来的 n - 1 行描述道路。其中第 i 行包含三个整数 ai、bi 和 ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 109, 1 ≤ i < n) — 第 i 条道路连接的村庄数量和道路长度。行中的数字由空格分隔。

下一行包含一个整数 q (1 ≤ q ≤ 105) — 查询数。然后按照q个查询,每行一个,按时间排序。每个查询属于以下三种类型之一:

- “+ x” — 村庄编号x恢复(1 ≤ x ≤ n)。
- “- x” — 编号x的村庄被摧毁(1 ≤ x ≤ n)。
- “?” — 考古学家想知道那个时期使用的道路的总长度。

保证查询不会相互矛盾,即不会有查询破坏不存在的村庄或恢复已存在的村庄。保证我们至少有一个“?”类型的查询。还保证人们可以通过给定的道路从任何一个村庄到达任何另一个村庄。

在最初的时刻,不认为存在任何村庄。

输出

对于每个“?”类型的查询在一行上打印已使用道路的总长度。您应该按照输入中给出的顺序打印查询的答案。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #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