QOJ.ac

QOJ

시간 제한: 2 s 메모리 제한: 512 MB 총점: 100 해킹 가능 ✓

#21438. Another Story END

통계

……除了一個圓滿的結局,你還想要什麼?

給定一棵有 $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$ 為端點的簡單路徑,包含該顏色的全部邊。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.