… Cos'altro potresti desiderare, oltre a un lieto fine?
Ti viene dato un albero con $n$ nodi numerati da $1$ a $n$, con radice nel nodo $1$. Per ogni $i = 2, 3, \ldots, n$, c'è un arco bidirezionale tra il nodo $i$ e il suo genitore $p_i$ con colore $c_i$ e lunghezza $w_i$.
Per un colore $c$ che appare nell'albero, se un cammino semplice passa per tutti gli archi di colore $c$, oppure non passa per alcun arco di colore $c$, allora il colore $c$ si dice buono per questo cammino; altrimenti, il colore $c$ si dice cattivo per questo cammino.
Dato un intero $k \in \{0, 1\}$, trova la lunghezza massima di un cammino semplice con al più $k$ colori cattivi. La lunghezza di un cammino è definita come la somma delle lunghezze di tutti gli archi sul cammino.
Puoi scegliere lo stesso nodo come entrambi gli estremi del cammino; in questo caso, il cammino non passa per alcun arco e ha lunghezza $0$.
Nota che gli archi dello stesso colore non sono necessariamente connessi e la lunghezza di un arco può essere $0$.
Input
La prima riga contiene due interi $n, k$, che rappresentano rispettivamente il numero di nodi e il numero massimo consentito di colori cattivi.
La $i$-esima delle successive $n - 1$ righe contiene tre interi $p_i, c_i, w_i$, che indicano che c'è un arco bidirezionale tra il nodo $i$ e il nodo $p_i$ di colore $c_i$ e lunghezza $w_i$.
Output
Stampa una singola riga contenente un intero, che rappresenta la lunghezza massima di un cammino semplice con al più $k$ colori cattivi.
Esempi
Input 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Output 1
108
Note
Scegli il cammino dal nodo $5$ al nodo $6$, passando nell'ordine per i nodi $5, 1, 6$, con lunghezza $8 + 100 = 108$.
Questo cammino non passa per alcun arco di colore $1$ e passa per tutti gli archi di colore $3$, quindi i colori $1, 3$ sono entrambi buoni. Passa solo per uno dei due archi di colore $2$, quindi il colore $2$ è cattivo.
Questo cammino ha esattamente un colore cattivo, soddisfacendo la richiesta. Si può dimostrare che non esiste alcun cammino valido più lungo.
Input 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
Output 2
35
Note
Scegli il cammino dal nodo $8$ al nodo $9$, passando nell'ordine per i nodi $8, 4, 2, 1, 3, 6, 9$, con lunghezza $8 + 5 + 3 + 4 + 6 + 9 = 35$.
Questo cammino passa per tutti gli archi dei colori $1, 2, 5$ e per nessun arco dei colori $3, 4$, quindi non ha colori cattivi e soddisfa la richiesta. Si può dimostrare che non esiste alcun cammino valido più lungo.
Input 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
Output 3
16
Note
Scegli il cammino dal nodo $7$ al nodo $8$, passando nell'ordine per i nodi $7, 2, 1, 3, 8$, con lunghezza $2 + 6 + 5 + 3 = 16$.
Questo cammino passa per due dei tre archi di colore $1$, quindi il colore $1$ è cattivo. Passa per tutti gli archi dei colori $3, 4$ e per nessun arco di altri colori, quindi ha esattamente un colore cattivo e soddisfa la richiesta.
Il cammino dal nodo $7$ al nodo $9$ ha lunghezza $17$, ma i colori $1, 2$ sono entrambi cattivi, quindi non soddisfa la richiesta. Si può dimostrare che non esiste alcun cammino valido di lunghezza superiore a $16$.
Limiti
Per tutti i dati di test, vale quanto segue:
- $2 \le n \le 2 \times 10^5$;
- $k \in \{0, 1\}$;
- Per ogni $i = 2, 3, \ldots, n$, vale $1 \le p_i < i$, $1 \le c_i \le n$ e $0 \le w_i \le 10^9$.
Subtask
Questo problema utilizza test a gruppi (bundled testing) con ragionevoli dipendenze tra subtask.
| Subtask | $n \le$ | $k =$ | Proprietà speciale | Punteggio |
|---|---|---|---|---|
| $1$ | $200$ | $0$ o $1$ | Nessuna | $5$ |
| $2$ | $3000$ | $0$ o $1$ | Nessuna | $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$ | Nessuna | $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$ | Nessuna | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | Nessuna | $13$ |
- Proprietà speciale A: Per ogni colore, tutti gli archi di quel colore formano un sottografo connesso.
- Proprietà speciale B: Ogni colore appare al massimo due volte.
- Proprietà speciale C: Per ogni $i = 2, 3, \ldots, n$, $p_i$ è generato in modo indipendente e uniformemente a caso tra gli interi $1, 2, \ldots, i - 1$.
- Proprietà speciale D: Per ogni colore, esiste un cammino semplice avente il nodo $1$ come uno dei suoi estremi che contiene tutti gli archi di quel colore.