QOJ.ac

QOJ

実行時間制限: 2 s メモリ制限: 512 MB 満点: 100 ハック可能 ✓

#21438. Another Story END

統計

… 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.

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.