tree

Étant donné un arbre non orienté avec des poids (potentiellement négatifs) sur les arêtes vous devez calculer un chemin de poids maximum. Par convention un chemin de longueur nulle à poids nul.

Le fichier commence avec T le nombre de testcases. Chaque testcase contient un entier n le nombre d'arête. Puis n lignes représentant chaque arête. Chaque ligne est composée de trois entiers: le numéro du sommet de départ, le numéro du sommet d'arrivé et la valeur de l'arête.

Limites et formatage

Chaque réponse commencera par Case #i: avec i le numéro du testcase (en commençant à 1). Votre programme doit retourner le bon résultat en moins de 10 secondes compilé avec -O2 sur une des machines de l'école. Pour ce problème seulement 5 testcases sont gros (n=100000).

Input

20
4
0 4 -3
1 4 -3
2 3 -8
3 4 10
4
0 3 3
0 4 10
1 2 -1
1 3 -2
4
0 4 -2
1 2 -9
1 3 -4
1 4 -8
4
0 2 -10
0 3 10
1 4 -10
3 4 -5
4
0 2 6
0 3 -6
1 4 -6
2 4 0
4
0 1 8
0 3 9
1 2 5
2 4 4
4
0 2 -9
1 4 -7
2 3 -4
2 4 -1
4
0 1 4
0 3 6
0 4 -6
2 3 7
4
0 2 4
1 2 3
2 4 -2
3 4 2
4
0 2 -3
1 3 -9
2 4 -10
3 4 8
9
0 1 -3
0 4 -3
0 7 -8
1 2 10
3 4 3
4 5 10
5 6 -1
6 8 -2
8 9 -2
9
0 1 -9
0 8 -4
1 6 -8
1 7 -10
2 8 10
3 8 -10
4 8 -5
4 9 6
5 7 -6
9
0 5 -6
0 9 0
1 3 8
1 4 9
1 5 5
1 6 4
2 5 -9
4 8 -7
5 7 -4
9
0 4 -1
0 7 4
1 6 6
2 3 -6
2 4 7
2 8 4
5 7 3
5 9 -2
6 9 2
9
0 2 -3
0 4 -9
0 8 -10
1 7 8
1 9 3
2 6 4
3 5 -3
5 8 -10
7 8 -8
9
0 8 -5
1 5 1
1 7 -6
1 8 -4
2 5 6
3 4 -8
3 9 -5
5 6 -3
7 9 -9
9
0 1 -3
0 4 7
0 6 -1
0 8 4
2 8 -4
2 9 -3
3 4 9
4 5 -3
5 7 2
9
0 2 7
0 8 -2
1 4 -9
1 5 -10
2 5 -10
3 5 -1
3 7 0
3 9 -3
6 9 3
9
0 3 9
0 7 3
1 6 -10
1 7 -9
2 3 4
2 5 2
4 8 10
6 8 -5
6 9 -4
9
0 5 0
0 6 -10
1 5 -3
2 6 -2
3 5 7
4 6 8
4 7 7
5 9 -7
7 8 -7

Télécharger l'entrée

Output

Case #1: 10
Case #2: 13
Case #3: 0
Case #4: 10
Case #5: 6
Case #6: 26
Case #7: 0
Case #8: 17
Case #9: 7
Case #10: 8
Case #11: 14
Case #12: 11
Case #13: 17
Case #14: 23
Case #15: 11
Case #16: 7
Case #17: 20
Case #18: 7
Case #19: 18
Case #20: 15

Télécharger la sortie

Il faut être logué pour pouvoir envoyer une soumission.