QOJ.ac

QOJ

Límite de tiempo: 2 s Límite de memoria: 512 MB Puntuación total: 100 Hackeable ✓

#21438. Another Story END

Estadísticas

……除咗一個圓滿嘅結局,你仲想要啲咩?

畀一棵有 $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.