……除咗一個圓滿嘅結局,你仲想要啲咩?
畀一棵有 $n$ 個節點嘅樹,節點編號由 $1$ 到 $n$,以節點 $1$ 為根。對於每個 $i = 2, 3, \ldots, n$,節點 $i$ 同佢嘅父節點 $p_i$ 之間有一條雙向邊,呢條邊嘅顏色係 $c_i$,長度係 $w_i$。
對於樹入面出現過嘅一種顏色 $c$,如果一條簡單路徑經過晒所有顏色係 $c$ 嘅邊,或者冇經過任何顏色係 $c$ 嘅邊,就稱顏色 $c$ 對呢條路徑係好嘅;否則,稱顏色 $c$ 對呢條路徑係壞嘅。
畀一個整數 $k \in \{0, 1\}$,請你求出壞顏色數量唔超過 $k$ 嘅簡單路徑嘅最大長度。路徑嘅長度定義為路徑上所有邊嘅長度之和。
你可以揀同一個節點作為路徑嘅兩個端點,呢個時候路徑唔經過任何邊,長度係 $0$。
請注意,同一種顏色嘅邊唔一定連通,邊嘅長度可以係 $0$。
輸入格式
第一行包含兩個整數 $n, k$,分別表示節點數量同埋容許嘅壞顏色數量上限。
接落嚟 $n - 1$ 行嘅第 $i$ 行包含三個整數 $p_i, c_i, w_i$,表示節點 $i$ 同節點 $p_i$ 之間有一條顏色係 $c_i$、長度係 $w_i$ 嘅雙向邊。
輸出格式
輸出一行一個整數,表示壞顏色數量唔超過 $k$ 嘅簡單路徑嘅最大長度。
範例
輸入格式 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
輸出格式 1
108
說明
揀由節點 $5$ 到節點 $6$ 嘅路徑,依次經過節點 $5, 1, 6$,長度係 $8 + 100 = 108$。
呢條路徑冇經過顏色係 $1$ 嘅邊,經過晒全部顏色係 $3$ 嘅邊,所以顏色 $1, 3$ 都係好嘅。佢只係經過咗兩條顏色係 $2$ 嘅邊入面嘅一條,所以顏色 $2$ 係壞嘅。
呢條路徑恰好有一種壞顏色,滿足要求,可以證明唔存在更長嘅合法路徑。
輸入格式 2
10 0 1 1 3 1 2 4 2 1 5 2 3 40 3 2 6 3 4 2 4 5 8 6 5 9 7 3 10
輸出格式 2
35
說明
揀由節點 $8$ 到節點 $9$ 嘅路徑,依次經過節點 $8, 4, 2, 1, 3, 6, 9$,長度係 $8 + 5 + 3 + 4 + 6 + 9 = 35$。
呢條路徑經過晒顏色 $1, 2, 5$ 嘅全部邊,冇經過顏色 $3, 4$ 嘅任何邊,所以冇壞顏色,滿足要求,可以證明唔存在更長嘅合法路徑。
輸入格式 3
10 1 1 1 6 1 1 5 1 1 0 1 2 8 1 2 0 2 3 2 3 4 3 5 5 1 6 6 4
輸出格式 3
16
說明
揀由節點 $7$ 到節點 $8$ 嘅路徑,依次經過節點 $7, 2, 1, 3, 8$,長度係 $2 + 6 + 5 + 3 = 16$。
呢條路徑經過咗顏色 $1$ 嘅三條邊入面嘅兩條,所以顏色 $1$ 係壞嘅。佢經過晒顏色 $3, 4$ 嘅全部邊,冇經過其他顏色嘅任何邊,所以恰好有一種壞顏色,滿足要求。
由節點 $7$ 到節點 $9$ 嘅路徑長度係 $17$,但係顏色 $1, 2$ 都係壞嘅,唔滿足要求。可以證明唔存在長度超過 $16$ 嘅合法路徑。
資料範圍
對於所有數據,滿足:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- 對於每個 $i = 2, 3, \ldots, n$,有 $1 \le p_i < i$、$1 \le c_i \le n$、$0 \le w_i \le 10^9$。
子任務
本題採用捆綁測試,而且開啟咗合理嘅子任務依賴。
| 子任務編號 | $n \le$ | $k =$ | 特殊性質 | 分值 |
|---|---|---|---|---|
| $1$ | $200$ | $0$ 或 $1$ | 冇 | $5$ |
| $2$ | $3000$ | $0$ 或 $1$ | 冇 | $9$ |
| $3$ | $2 \times 10^5$ | $0$ | A | $4$ |
| $4$ | $2 \times 10^5$ | $0$ | B | $5$ |
| $5$ | $2 \times 10^5$ | $0$ | C | $3$ |
| $6$ | $2 \times 10^5$ | $0$ | D | $4$ |
| $7$ | $2 \times 10^5$ | $0$ | 冇 | $7$ |
| $8$ | $2 \times 10^5$ | $1$ | A | $8$ |
| $9$ | $2 \times 10^5$ | $1$ | B | $14$ |
| $10$ | $2 \times 10^5$ | $1$ | C | $9$ |
| $11$ | $2 \times 10^5$ | $1$ | D | $8$ |
| $12$ | $10^5$ | $1$ | 冇 | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | 冇 | $13$ |
- 特殊性質 A:對於每種顏色,該顏色嘅全部邊構成連通子圖。
- 特殊性質 B:每種顏色最多出現兩次。
- 特殊性質 C:對於每個 $i = 2, 3, \ldots, n$,$p_i$ 獨立咁由整數 $1, 2, \ldots, i - 1$ 入面等概率隨機生成。
- 特殊性質 D:對於每種顏色,存在一條以節點 $1$ 為端點嘅簡單路徑,包含該顏色嘅全部邊。