TopCoder

User's AC Ratio

78.6% (22/28)

Submission's AC Ratio

27.1% (51/188)

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

No. Testdata Range Score
1 0~4 7
2 5~9 17
3 10~14 22
4 15~19 25
5 20~24 29

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 102400 262144 1
1 1000 102400 262144 1
2 1000 102400 262144 1
3 1000 102400 262144 1
4 1000 102400 262144 1
5 3000 102400 262144 2
6 3000 102400 262144 2
7 3000 102400 262144 2
8 3000 102400 262144 2
9 3000 102400 262144 2
10 1000 102400 262144 3
11 1000 102400 262144 3
12 1000 102400 262144 3
13 1000 102400 262144 3
14 1000 102400 262144 3
15 1000 102400 262144 4
16 1000 102400 262144 4
17 1000 102400 262144 4
18 1000 102400 262144 4
19 1000 102400 262144 4
20 4500 102400 262144 5
21 4500 102400 262144 5
22 4500 102400 262144 5
23 4500 102400 262144 5
24 4500 102400 262144 5