……除了一個圓滿的結局,你還想要什麼?
給定一棵有 $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$ 為端點的簡單路徑,包含該顏色的全部邊。