TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

77.8% (14/18)

Submission's AC Ratio

20.0% (27/135)

Description

「我要成為海賊王!!!!」

在遙遠星球上的外星人,氌枹,看到了這激勵人心的漫畫之後,從椅子上跳了下來,如此地說道。

經過五年的準備後,氌枹召募了船員 ,準備好了船隻,準備實現他長久以來的遠望。然而,當他從島上出發後,他發現一件殘酷的事實:
這個星球上共有$N$座島,編號$0$到$N-1$(其中$0$號島就是他的出發地),由$N-1$條雙向航道連接,而且任兩個島之間都恰由一系列的航道連接。

「這世界真是太無聊了!」氌枹如此感嘆道。

為了增加航程的樂趣,他決定不時就丟棄船員在島上,並且在其它島上使用望遠鏡看著他們受苦受難,得到無止盡的快感。雖然有些病態,不過讓我們先把氌枹得到的快感量化吧:
如果有個船員被丟棄在A島,而氌枹在B島,那麼氌枹偷窺在A島上的船員所得到的快感就是A島到B島之間的距離(距離愈遠,氌枹愈有凌虐船員的優越感)。而氌枹從B島可以看到所有的$N$個島,所以他所得到的快感即為$N$個島上所有船員貢獻的快感之和。不過,看著同個島上的兩名船員受苦並不會給予氌枹兩倍的快感,也就是說一個島上有一名船員和有任意多名船員給予氌枹的快感都是一樣的。

你,遙遠星球上的航警,在路上撿到了氌枹的航行日誌。上面詳細地記載了氌枹從出航以來,丟棄船員以及暫時停靠的時間以及位置。為了懲罰這病態,你決定將他的罪狀條列給最高航海法庭審理。對於氌枹的每次停靠,請你計算出他所獲得的快感的大小。

Input Format

第一行有兩個正整數$N\leq 10^ 5, Q\leq 10^ 6$代表島的數量以及航行日誌上記載的事件數。
接下來的$N-1$ 行分別有三個正整數$a_i, b_i, l_i$,代表編號$a_i$和編號$b_i$的島之間由一條長度為$1\leq l_i\leq 10^ 7$的航道連接。為了方便起見,$0\leq a_i < b_i = i$,其中$i=1,2,...,N-1$。
接下來的$Q$行分別有兩個正整數$t, x$,代表航行日誌上所記載的事件。如果$t$是1,代表氌枹丟了一名船員到編號是$x$的島。如果$t$是2,代表氌枹暫時停靠在編號是$x$的島。

子任務(測資) 額外限制 分數
1 (0~4) $Q\leq 10^ 4$,至多丟下100名船員 13
2 (5~9) 所有停靠紀錄都在拋下船員之後 13
3 (10~14) $Q\leq 10^ 5$ 25
4 (15~19) 無限制 49

Output Format

對於每次氌枹的停靠紀錄,輸出他當時可以得到的快感大小。

Sample Input

4 5
0 1 40
1 2 11
1 3 18
2 3
1 2
1 2
1 0
2 3

Sample Output

0
87

Hints

本題的輸出輸入有點多。如果是使用C++式輸出輸入者,建議加入std::ios::sync_with_stdio(0), std::cin.tie(0);以及用'\n'替代std::endl增快輸出輸入速度。如果加入了std::ios::sync_with_stdio(0), std::cin.tie(0);,請勿同時使用C式以及C++式輸出輸入。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第三次模擬賽pF
題目取自2015 TOI第二階段選訓第四次模擬考pA
(原題範圍皆只到$10^ 5$)

Subtasks

For Testdata: 0 ~ 4, Score: 13
For Testdata: 5 ~ 9, Score: 13
For Testdata: 10 ~ 14, Score: 25
For Testdata: 15 ~ 20, Score: 49
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 204800 65536
1 1000 204800 65536
2 1000 204800 65536
3 1000 204800 65536
4 1000 204800 65536
5 1000 204800 65536
6 1000 204800 65536
7 1000 204800 65536
8 1000 204800 65536
9 1000 204800 65536
10 1000 204800 65536
11 1000 204800 65536
12 1000 204800 65536
13 1000 204800 65536
14 1000 204800 65536
15 1500 204800 65536
16 1500 204800 65536
17 1500 204800 65536
18 1500 204800 65536
19 1500 204800 65536
20 1500 204800 65536