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

……円満な結末以外に、あなたが望むものは何ですか?

$1$ から $n$ までの番号がついた $n$ 頂点の木が与えられます。根は頂点 $1$ です。各 $i = 2, 3, \ldots, n$ について、頂点 $i$ とその親 $p_i$ の間には双方向の辺があり、この辺の色は $c_i$、長さは $w_i$ です。

木に現れる色 $c$ について、ある単純パスが色 $c$ の辺をすべて通るか、あるいは色 $c$ の辺を1本も通らないとき、色 $c$ はこのパスにとって良い色であるといいます。そうでないとき、色 $c$ はこのパスにとって悪い色であるといいます。

整数 $k \in \{0, 1\}$ が与えられます。悪い色の個数が $k$ 以下の単純パスの長さの最大値を求めてください。パスの長さは、パス上のすべての辺の長さの総和として定義されます。

パスの両端点として同じ頂点を選ぶこともできます。この場合、パスは辺を1本も通らず、長さは $0$ となります。

同じ色の辺が連結であるとは限らず、辺の長さが $0$ である場合もあることに注意してください。

入力

1行目には2つの整数 $n, k$ が与えられ、それぞれ頂点数と許容される悪い色の個数の上限を表します。

続く $n - 1$ 行のうち $i$ 行目には3つの整数 $p_i, c_i, w_i$ が与えられ、頂点 $i$ と頂点 $p_i$ の間に色 $c_i$、長さ $w_i$ の双方向の辺があることを表します。

出力

悪い色の個数が $k$ 以下の単純パスの長さの最大値を表す整数を1行に出力してください。

入出力例

入力 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$ の辺を1本も通らず、色 $3$ の辺をすべて通るため、色 $1, 3$ はともに良い色です。色 $2$ の2本の辺のうち1本だけを通るため、色 $2$ は悪い色です。

このパスには悪い色がちょうど1種類あり、条件を満たします。これより長い条件を満たすパスが存在しないことが証明できます。

入力 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$ の辺を1本も通らないため、悪い色はなく条件を満たします。これより長い条件を満たすパスが存在しないことが証明できます。

入力 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$ の3本の辺のうち2本を通るため、色 $1$ は悪い色です。色 $3, 4$ のすべての辺を通り、その他の色の辺を1本も通らないため、悪い色はちょうど1種類であり、条件を満たします。

頂点 $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:各色は高々2回しか現れない。
  • 特殊な性質 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.