300924: CF176E. Archaeology

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Archaeology

题意翻译

有一棵 $n$ 个点的带权树,每个点都是黑色或白色,最初所有点都是白色的。有 $q$ 个询问: - 把点 $x$ 从白色变成黑色。 - 把点 $x$ 从黑色变成白色。 - 查询黑点的导出子树 $($用最少的边把**所有的**黑点连通起来的树$)$ 的总边权和。 保证 $1 \leq n, q \leq 10^5, 1 \leq x \leq n$。

题目描述

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 destroyed completely. 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.

输入输出格式

输入格式


The first line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ) — 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}<=10^{9} $ , $ 1<=i&lt;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<=10^{5} $ ) — 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.

输出格式


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 С++. It is preferred to use cin, cout streams or the %I64d specifier.

输入输出样例

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

Input

题意翻译

有一棵 $n$ 个点的带权树,每个点都是黑色或白色,最初所有点都是白色的。有 $q$ 个询问: - 把点 $x$ 从白色变成黑色。 - 把点 $x$ 从黑色变成白色。 - 查询黑点的导出子树 $($用最少的边把**所有的**黑点连通起来的树$)$ 的总边权和。 保证 $1 \leq n, q \leq 10^5, 1 \leq x \leq n$。

加入题单

上一题 下一题 算法标签: