CF176E.Archaeology

This time you should help a team of researchers on an island in the Pacific Ocean. They research the culture of the ancient tribes that used to inhabit the island many years ago.

Overall they've dug out n villages. Some pairs of villages were connected by roads. People could go on the roads in both directions. Overall there were exactly n - 1 roads, and from any village one could get to any other one.

The tribes were not peaceful, and they had many wars. As a result of the wars, some villages were completely destroyed. During more peaceful years, some of the villages were restored.

At each moment of time, people used only those roads that belonged to some shortest way between two villages that existed at the given moment. In other words, people used the minimum subset of roads in such a way that it was possible to get from any existing village to any other existing one. Note that throughout the island's whole history, there existed exactly n - 1 roads that have been found by the researchers. There never were any other roads.

The researchers think that observing the total sum of used roads' lengths at different moments of time can help to better understand the tribes' culture and answer several historical questions.

You will be given the full history of the tribes' existence. Your task is to determine the total length of used roads at some moments of time.

这一次，你需要帮助一支位于太平洋某岛屿上的科研团队。他们正在研究多年前曾居住在该岛上的古代部落的文化。

迄今为止，他们共发掘出 $n$ 个村庄。某些村庄对之间由道路相连，道路为双向通行。总共恰好有 $n-1$ 条道路，且任意两个村庄之间均可相互到达（即整个道路网络构成一棵树）。

这些部落并不和平，彼此间爆发过多次战争。受战争影响，部分村庄被彻底摧毁。而在相对和平的年代，一些村庄又得以重建。

在任一时刻，人们仅使用那些属于当时尚存村庄两两之间某条最短路径的道路。换言之，人们所使用的道路集合是满足“任意现存村庄均可到达其余任意现存村庄”这一条件的最小道路子集（即现存村庄构成的子图的最小生成树——由于原图是一棵树，这等价于现存村庄所诱导的子图的最小连通子树）。注意：在整个岛屿历史中，研究人员所发现的道路始终严格为 $n-1$ 条，从未存在过其他道路。

研究人员推测，观测不同时刻所使用道路的总长度，将有助于更深入地理解部落文化，并解答若干历史问题。

你将获得该部落存在的完整历史记录。你的任务是计算若干特定时刻所使用道路的总长度。

The first line contains an integer n (1 ≤ n ≤ 105) — the number of villages. The next n - 1 lines describe the roads. The i-th of these lines contains three integers a__i, b__i, and c__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i, 1 ≤ c__i ≤ 109, 1 ≤ i < n) — the numbers of villages that are connected by the i-th road and the road's length. The numbers in the lines are separated by a space.

The next line contains an integer q (1 ≤ q ≤ 105) — the number of queries. Then follow q queries, one per line, ordered by time. Each query belongs to one of three types:

• "+ x" — village number x is restored (1 ≤ x ≤ n).
• "- x" — village number x is destroyed (1 ≤ x ≤ n).
• "?" — the archaeologists want to know the total length of the roads which were used for that time period.

It is guaranteed that the queries do not contradict each other, that is, there won't be queries to destroy non-existing villages or restore the already existing ones. It is guaranteed that we have at least one query of type "?". It is also guaranteed that one can get from any village to any other one by the given roads.

At the initial moment of time, no village is considered to exist.

第一行包含一个整数 $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$ 条道路所连接的两个村庄编号及其长度。每行中的数字以空格分隔。

接下来一行包含一个整数 $q$（$1 \leq q \leq 10^5$）—— 查询的数量。随后是 $q$ 个查询，每行一个，按时间顺序给出。每个查询属于以下三种类型之一：

• “+ x” —— 村庄编号 $x$ 被恢复（$1 \leq x \leq n$）；
• “- x” —— 村庄编号 $x$ 被摧毁（$1 \leq x \leq n$）；
• “?” —— 考古学家希望知道当前时间段内所使用的道路的总长度。

保证所有查询互不矛盾，即不会出现对不存在的村庄执行摧毁操作，也不会对已存在的村庄执行恢复操作。保证至少存在一个类型为 ? 的查询。还保证：给定的道路可使任意两个村庄之间相互连通。

在初始时刻，没有任何村庄被视为存在。

For each query of type "?" print the total length of used roads on a single line. You should print the answers to the queries in the order in which they are given in the input.

Please do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use cin, cout streams, or the %I64d specifier.

对于每个类型为 “?” 的查询，请在单独一行输出已使用道路的总长度。
请按照输入中给出查询的顺序输出对应答案。

在 C++ 中，请勿使用 %lld 说明符读取或写入 64 位整数。推荐使用 cin/cout 流，或 %I64d 说明符。