原題來(lái)自：Contest Hunter Round #56

在 Adera 的異時(shí)空中有一張地圖。這張地圖上有 N 個(gè)點(diǎn)，有 N?1 條雙向邊把它們連通起來(lái)。起初地圖上沒(méi)有任何異象石，在接下來(lái)的 M 個(gè)時(shí)刻中，每個(gè)時(shí)刻會(huì)發(fā)生以下三種類(lèi)型的事件之一：

地圖的某個(gè)點(diǎn)上出現(xiàn)了異象石（已經(jīng)出現(xiàn)的不會(huì)再次出現(xiàn)）；

地圖某個(gè)點(diǎn)上的異象石被摧毀（不會(huì)摧毀沒(méi)有異象石的點(diǎn)）；

向玩家詢問(wèn)使所有異象石所在的點(diǎn)連通的邊集的總長(zhǎng)度最小是多少。

請(qǐng)你作為玩家回答這些問(wèn)題。下圖是一個(gè)例子，灰色節(jié)點(diǎn)表示出現(xiàn)了異象石，加粗的邊表示被選為連通異象石的邊集。

第一行有一個(gè)整數(shù) N，表示點(diǎn)的個(gè)數(shù)；

接下來(lái) N?1 行每行三個(gè)整數(shù) x,y,z，表示點(diǎn) x 和 y 之間有一條長(zhǎng)度為 z 的雙向邊；

第 N+1 行有一個(gè)正整數(shù) M；

接下來(lái) M 行每行是一個(gè)事件，事件是以下三種格式之一：

+x：表示點(diǎn) x 上出現(xiàn)了異象石；

?x：表示點(diǎn) x 上的異象石被摧毀；

?：表示詢問(wèn)使當(dāng)前所有異象石所在的點(diǎn)連通所需的邊集的總長(zhǎng)度最小是多少。

對(duì)于每個(gè) ? 事件，輸出一個(gè)整數(shù)表示答案。

數(shù)據(jù)范圍與提示：

對(duì)于 30% 的數(shù)據(jù)，1≤?n,m?≤?10³ ；

對(duì)于另 20% 的數(shù)據(jù)，地圖是一條鏈，或者一朵菊花；

對(duì)于 100% 的數(shù)據(jù)，1≤?n,m?≤?10⁵,1?≤?x,y?≤?n,x≠?y,1?≤?z?≤?10⁹ 。

信息學(xué)一本通