Description

Xiao B is playing a treasure hunt game. The map has $N$ villages and $N-1$ roads, and there is exactly one path between any two villages. At the beginning, the player may choose any village and instantly teleport to it, then walk arbitrarily along the roads on the map. If the player reaches a village that contains a treasure, that treasure is considered found. The process continues until all treasures are found and the player returns to the village they initially teleported to.

Xiao B wants to evaluate the difficulty of this game, so he needs to know the shortest distance a player must walk to find all treasures. However, the treasures in this game change frequently: sometimes a treasure suddenly appears in a village, and sometimes a treasure in a village suddenly disappears. Therefore, Xiao B needs to update the data continuously. Since he is too lazy to do the calculations himself, he asks for your help. To simplify the problem, assume that initially no village contains a treasure.

Input Format

The first line contains two integers $N, M$, where $M$ is the number of treasure changes.

The next $N-1$ lines each contain three integers $x, y, z$, indicating that there is a road of length $z$ between villages $x$ and $y$.

The next $M$ lines each contain one integer $t$, representing a treasure toggle operation. If before this operation village $t$ does not contain a treasure, then after the operation it contains a treasure; if before the operation village $t$ contains a treasure, then after the operation it does not.

Output Format

Output $M$ lines, each containing one integer. The integer on the $i$-th line is the shortest distance the player needs to walk to find all treasures after the $i$-th operation. If there is only one village with a treasure, or no village has a treasure, output 0.

4 5
1 2 30
2 3 50
2 4 60
2
3
4
2
1

0
100
220
220
280

Hint

• For 10% of the testdata, $1 \leq N \leq 100, 1 \leq M \leq 100$.
• For 20% of the testdata, $1 \leq N \leq 1000, 1 \leq M \leq 1000$.
• For another 15% of the testdata, each village is incident to at most two roads.
• For 100% of the testdata, $1 \leq N \leq 100000,\ 1 \leq M \leq 100000,\ 1 \leq z \leq 10^9$.

Translated by ChatGPT 5