… Qu'espérer de plus qu'une fin heureuse ?
On vous donne un arbre à $n$ sommets numérotés de $1$ à $n$, enraciné au sommet $1$. Pour chaque $i = 2, 3, \ldots, n$, il y a une arête bidirectionnelle entre le sommet $i$ et son parent $p_i$, de couleur $c_i$ et de longueur $w_i$.
Pour une couleur $c$ présente dans l'arbre, si un chemin simple passe par toutes les arêtes de couleur $c$, ou ne passe par aucune arête de couleur $c$, alors la couleur $c$ est dite bonne pour ce chemin ; sinon, la couleur $c$ est dite mauvaise pour ce chemin.
Étant donné un entier $k \in \{0, 1\}$, trouvez la longueur maximale d'un chemin simple ayant au plus $k$ mauvaises couleurs. La longueur d'un chemin est définie comme la somme des longueurs de toutes les arêtes sur ce chemin.
Vous pouvez choisir le même sommet comme les deux extrémités du chemin ; dans ce cas, le chemin ne passe par aucune arête et sa longueur est $0$.
Veuillez noter que les arêtes d'une même couleur ne sont pas nécessairement connexes, et que la longueur d'une arête peut être égale à $0$.
Entrée
La première ligne contient deux entiers $n, k$, représentant respectivement le nombre de sommets et le nombre maximum autorisé de mauvaises couleurs.
La $i$-ème des $n - 1$ lignes suivantes contient trois entiers $p_i, c_i, w_i$, indiquant qu'il existe une arête bidirectionnelle entre le sommet $i$ et le sommet $p_i$ de couleur $c_i$ et de longueur $w_i$.
Sortie
Affichez une seule ligne contenant un entier, représentant la longueur maximale d'un chemin simple ayant au plus $k$ mauvaises couleurs.
Exemples
Entrée 1
6 1 1 1 1 1 1 4 1 2 2 1 2 8 1 3 100
Sortie 1
108
Remarque
Choisissons le chemin du sommet $5$ au sommet $6$, passant successivement par les sommets $5, 1, 6$, de longueur $8 + 100 = 108$.
Ce chemin ne passe par aucune arête de couleur $1$ et passe par toutes les arêtes de couleur $3$, donc les couleurs $1, 3$ sont toutes deux bonnes. Il ne passe que par l'une des deux arêtes de couleur $2$, donc la couleur $2$ est mauvaise.
Ce chemin a exactement une mauvaise couleur, ce qui satisfait la condition. On peut prouver qu'il n'existe aucun chemin valide plus long.
Entrée 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
Sortie 2
35
Remarque
Choisissons le chemin du sommet $8$ au sommet $9$, passant successivement par les sommets $8, 4, 2, 1, 3, 6, 9$, de longueur $8 + 5 + 3 + 4 + 6 + 9 = 35$.
Ce chemin passe par toutes les arêtes des couleurs $1, 2, 5$ et par aucune arête des couleurs $3, 4$, il n'a donc aucune mauvaise couleur et satisfait la condition. On peut prouver qu'il n'existe aucun chemin valide plus long.
Entrée 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
Sortie 3
16
Remarque
Choisissons le chemin du sommet $7$ au sommet $8$, passant successivement par les sommets $7, 2, 1, 3, 8$, de longueur $2 + 6 + 5 + 3 = 16$.
Ce chemin passe par deux des trois arêtes de couleur $1$, donc la couleur $1$ est mauvaise. Il passe par toutes les arêtes des couleurs $3, 4$ et par aucune arête d'une autre couleur, il a donc exactement une mauvaise couleur et satisfait la condition.
Le chemin du sommet $7$ au sommet $9$ a une longueur de $17$, mais les couleurs $1, 2$ sont toutes deux mauvaises, ce qui ne satisfait pas la condition. On peut prouver qu'il n'existe aucun chemin valide de longueur supérieure à $16$.
Contraintes
Pour toutes les données de test, les conditions suivantes sont vérifiées :
- $2 \le n \le 2 \times 10^5$ ;
- $k \in \{0, 1\}$ ;
- Pour chaque $i = 2, 3, \ldots, n$, on a $1 \le p_i < i$, $1 \le c_i \le n$ et $0 \le w_i \le 10^9$.
Sous-tâches
Ce problème utilise des tests groupés avec des dépendances raisonnables entre les sous-tâches.
| Sous-tâche | $n \le$ | $k =$ | Propriété spéciale | Points |
|---|---|---|---|---|
| $1$ | $200$ | $0$ ou $1$ | Aucune | $5$ |
| $2$ | $3000$ | $0$ ou $1$ | Aucune | $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$ | Aucune | $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$ | Aucune | $11$ |
| $13$ | $2 \times 10^5$ | $1$ | Aucune | $13$ |
- Propriété spéciale A : Pour chaque couleur, toutes les arêtes de cette couleur forment un sous-graphe connexe.
- Propriété spéciale B : Chaque couleur apparaît au plus deux fois.
- Propriété spéciale C : Pour chaque $i = 2, 3, \ldots, n$, $p_i$ est choisi indépendamment et uniformément au hasard parmi les entiers $1, 2, \ldots, i - 1$.
- Propriété spéciale D : Pour chaque couleur, il existe un chemin simple ayant le sommet $1$ pour extrémité qui contient toutes les arêtes de cette couleur.