……円満な結末以外に、あなたが望むものは何ですか?
$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$ を一端とし、その色のすべての辺を含む単純パスが存在する。