...Selain akhir yang bahagia, apa lagi yang kau inginkan?
Diberikan sebuah pohon dengan $n$ simpul yang dinomori dari $1$ hingga $n$, dengan simpul $1$ sebagai akar. Untuk setiap $i = 2, 3, \ldots, n$, terdapat sebuah sisi dua arah antara simpul $i$ dan induknya $p_i$ dengan warna $c_i$ dan panjang $w_i$.
Untuk suatu warna $c$ yang muncul di pohon, jika sebuah lintasan sederhana melewati semua sisi berwarna $c$, atau tidak melewati satu pun sisi berwarna $c$, maka warna $c$ disebut baik untuk lintasan ini; jika tidak, warna $c$ disebut buruk untuk lintasan ini.
Diberikan sebuah bilangan bulat $k \in \{0, 1\}$, carilah panjang maksimum dari lintasan sederhana dengan paling banyak $k$ warna buruk. Panjang sebuah lintasan didefinisikan sebagai jumlah panjang semua sisi pada lintasan tersebut.
Anda dapat memilih simpul yang sama sebagai kedua ujung lintasan; dalam hal ini, lintasan tidak melewati sisi mana pun dan memiliki panjang $0$.
Perhatikan bahwa sisi-sisi dengan warna yang sama belum tentu terhubung, dan panjang sisi bisa bernilai $0$.
Masukan
Baris pertama berisi dua bilangan bulat $n, k$, masing-masing menyatakan jumlah simpul dan batas atas jumlah warna buruk yang diperbolehkan.
Baris ke-$i$ dari $n - 1$ baris berikutnya berisi tiga bilangan bulat $p_i, c_i, w_i$, yang menyatakan bahwa terdapat sisi dua arah antara simpul $i$ dan simpul $p_i$ dengan warna $c_i$ dan panjang $w_i$.
Keluaran
Keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan panjang maksimum dari lintasan sederhana dengan paling banyak $k$ warna buruk.
Contoh
Masukan 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Keluaran 1
108
Catatan
Pilih lintasan dari simpul $5$ ke simpul $6$, melewati simpul $5, 1, 6$ secara berurutan, dengan panjang $8 + 100 = 108$.
Lintasan ini tidak melewati sisi berwarna $1$ dan melewati semua sisi berwarna $3$, sehingga warna $1, 3$ keduanya baik. Lintasan ini hanya melewati satu dari dua sisi berwarna $2$, sehingga warna $2$ buruk.
Lintasan ini memiliki tepat satu warna buruk, sehingga memenuhi syarat. Dapat dibuktikan bahwa tidak ada lintasan valid yang lebih panjang.
Masukan 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
Keluaran 2
35
Catatan
Pilih lintasan dari simpul $8$ ke simpul $9$, melewati simpul $8, 4, 2, 1, 3, 6, 9$ secara berurutan, dengan panjang $8 + 5 + 3 + 4 + 6 + 9 = 35$.
Lintasan ini melewati semua sisi berwarna $1, 2, 5$ dan tidak melewati sisi mana pun berwarna $3, 4$, sehingga tidak ada warna buruk dan memenuhi syarat. Dapat dibuktikan bahwa tidak ada lintasan valid yang lebih panjang.
Masukan 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
Keluaran 3
16
Catatan
Pilih lintasan dari simpul $7$ ke simpul $8$, melewati simpul $7, 2, 1, 3, 8$ secara berurutan, dengan panjang $2 + 6 + 5 + 3 = 16$.
Lintasan ini melewati dua dari tiga sisi berwarna $1$, sehingga warna $1$ buruk. Lintasan ini melewati semua sisi berwarna $3, 4$ dan tidak melewati sisi warna lainnya, sehingga memiliki tepat satu warna buruk dan memenuhi syarat.
Lintasan dari simpul $7$ ke simpul $9$ memiliki panjang $17$, tetapi warna $1, 2$ keduanya buruk sehingga tidak memenuhi syarat. Dapat dibuktikan bahwa tidak ada lintasan valid dengan panjang lebih dari $16$.
Batasan
Untuk semua data uji, berlaku:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- Untuk setiap $i = 2, 3, \ldots, n$, berlaku $1 \le p_i < i$, $1 \le c_i \le n$, dan $0 \le w_i \le 10^9$.
Subsoal
Soal ini menggunakan penilaian berkelompok (bundled testing) dengan ketergantungan subsoal yang wajar.
| Subsoal | $n \le$ | $k =$ | Sifat Khusus | Poin |
|---|---|---|---|---|
| $1$ | $200$ | $0$ atau $1$ | Tidak ada | $5$ |
| $2$ | $3000$ | $0$ atau $1$ | Tidak ada | $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$ | Tidak ada | $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$ | Tidak ada | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | Tidak ada | $13$ |
- Sifat Khusus A: Untuk setiap warna, semua sisi dengan warna tersebut membentuk subgraf yang terhubung.
- Sifat Khusus B: Setiap warna muncul paling banyak dua kali.
- Sifat Khusus C: Untuk setiap $i = 2, 3, \ldots, n$, $p_i$ dipilih secara independen dan acak seragam dari bilangan bulat $1, 2, \ldots, i - 1$.
- Sifat Khusus D: Untuk setiap warna, terdapat sebuah lintasan sederhana dengan simpul $1$ sebagai salah satu ujungnya yang memuat semua sisi dengan warna tersebut.