TopCoder

Thumb nutella
NutellaTrash
https://polarzcoding.blogspot.com 可以來參觀一下><

User's AC Ratio

72.7% (16/22)

Submission's AC Ratio

24.6% (30/122)

Description

你聽過多層次傳銷嗎?這是一種商業行銷模式。

在這個系統裡,有一個發起人,是第一個會員。每個會員都可以去招攬新的會員,一旦A成功招攬到了B,則A是B的「介紹人」,B成為A的「下屬」。此時B也成了會員,可以去招攬更多的會員。在這個層次分明的結構裡,每一個會員可以有很多個下屬,但每一個會員只會有一個介紹人(發起人除外,他沒有介紹人)。

此外,我們將一個會員的所有下屬、所有下屬的所有下屬、……等等,全部統稱為該會員的「下線」。每個會員都可以從他任何下線的購買行為獲得利潤。

現在Phh多層次傳銷公司(以下簡稱P公司)共有N個會員。為了增加上下屬之間的溝通,也為了推銷他們的產品,P公司會不定期地舉行一個活動。每一次活動開始時,P公司會挑選一個「特派會員」,並交給他一張宣傳單。只要特派會員成功把這張宣傳單給他的每一個下線簽名,就視為「任務完成」,並且可以獲得鉅額獎金,他的下線也可以獲得分紅。

然而,為了驗證這張宣傳單確實有達到功能,P公司規定了宣傳單的傳遞與簽名方法:一律採用郵寄傳遞。並且,任何一個會員(包括特派會員本人)收到這張宣傳單之後,如果之前還沒簽過名,就必須在上面簽名;接著,只能把這張宣傳單寄給介紹人或任意一個下屬。
(要注意的是,不能將宣傳單直接寄給介紹人的介紹人,或者下屬的下屬等等。)
當然,如果特派會員收到宣傳單時,上面已經有所有下線的簽名,則任務完成,可以向P公司領取獎金。

P公司推動這個活動的負責人Remal,將所有會員編為0到N-1號,特別地,0號會員代表發起人。他也預先調查了所有會員的從屬關係,並且發現:對於任何兩人A, B使得A是B的介紹人,則宣傳單無論是從A寄到B、或是從B寄到A,都會花費MAB天的通信時間。

為了決定這個活動要挑選哪個會員做為「特派會員」可以讓宣傳效果最好,Remal想要知道如果挑選某個會員作為特派會員,則最少要經過幾天才能完成這個簽名任務。
然而,會員有時候會搬家,因此寄信時間也會發生改變,因此他還希望可以隨時改變兩人間通信時間的值,以方便未來的查詢。

而身為P公司的資訊管理者,你的任務就是幫助Remal寫一個查詢的程式。
為了你的方便,你可以假設任何會員收到宣傳單之後都可以立刻簽完名並寄出去。

Input Format

第一行有兩個正整數N, Q,分別代表P公司會員數量和Remal總共需要進行查詢和改變數據次數的總和。$N, Q \leq 10^ 6$。

接下來的N-1行,每行有三個數字A, B, MAB,代表編號A的會員是編號B的會員的介紹人,而他們之間的通信時間是MAB。$A, B < N$。

接下來有Q行,每一行代表一個Remal的操作。保證所有操作指定的會員都存在。
如果是0 D M,令編號D的會員的介紹人編號為C,則這個操作代表C和D的通信時間MCD變成了M。
如果是1 D,代表詢問若挑選編號D的會員作為特派會員,則至少要花費多少幾天才能完成任務。保證答案不超過int範圍。

子任務(測資) 額外限制 分數
1 (0~4) $N, Q \leq 10^ 5$;
保證通信時間不會改變
7
2 (5~9) $N, Q \leq 10^ 4$ 17
3 (10~14) $N \leq 10^ 5, Q \leq 10^ 4$ 22
4 (15~19) $N, Q \leq 10^ 5$ 25
5 (20~24) 29

Output Format

對於每一個詢問,輸出一行包含一個整數,代表完成任務的最少天數。

Sample Input

7 6
0 1 4
1 2 7
1 3 12
2 4 8
2 5 11
3 6 8
0 2 11
1 5
0 3 7
1 2
0 4 2
1 3

Sample Output

0
38
16

Hints

看清楚題目,下屬和下線是不一樣的東西喔。

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校隊選拔:複試pE

Subtasks

For Testdata: 0 ~ 4, Score: 7
For Testdata: 5 ~ 9, Score: 17
For Testdata: 10 ~ 14, Score: 22
For Testdata: 15 ~ 19, Score: 25
For Testdata: 20 ~ 24, Score: 29
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 102400 65536
1 1000 102400 65536
2 1000 102400 65536
3 1000 102400 65536
4 1000 102400 65536
5 3000 102400 65536
6 3000 102400 65536
7 3000 102400 65536
8 3000 102400 65536
9 3000 102400 65536
10 1000 102400 65536
11 1000 102400 65536
12 1000 102400 65536
13 1000 102400 65536
14 1000 102400 65536
15 1000 102400 65536
16 1000 102400 65536
17 1000 102400 65536
18 1000 102400 65536
19 1000 102400 65536
20 4500 102400 65536
21 4500 102400 65536
22 4500 102400 65536
23 4500 102400 65536
24 4500 102400 65536