Étant donné un arbre enraciné, vous voulez colorer les sommets avec des entiers (plus grands au sens large que 1), de sorte que deux sommets adjacents n’aient pas la même couleur et que la somme des couleurs pour tous les sommets soit minimale.
Entrée et sortie : Chaque instance commence par le nombre n (1 ≤ n ≤ 10000) de sommets de l’arbre qui sont numérotés de 0 à n − 1. Il y a ensuite n lignes, contenant un entier k le nombre de fils du sommet de la ième ligne puis k entiers, les fils du sommet i. Chaque instance est suivie par une ligne vide. Vous devez renvoyer la valeur du coloriage optimal (somme des couleurs pour tous les sommets) pour chaque instance (en allant à la ligne à chaque fois, mais sans sauter de ligne).
5
0
4 4 0 2 3
0
0
0
3
0
2 0 2
0
6
0
0
1 4
4 2 0 5 1
0
0
8
0
0
1 3
3 6 1 0
0
1 2
1 4
1 5
4
3 2 3 1
0
0
0
3
2 2 1
0
0
1
0
3
0
1 0
1 1
6
0
1 0
1 3
0
3 2 1 5
0
2
0
1 0
6
0
1 0
0
0
4 1 3 5 2
0
10
0
1 0
3 3 1 4
4 9 5 7 8
1 6
0
0
0
0
0
4
0
1 3
1 1
1 0
8
3 3 1 5
0
0
4 6 7 4 2
0
0
0
0
12
0
3 6 7 8
0
0
0
2 10 2
4 4 3 9 0
0
0
0
0
2 1 5
12
0
4 7 0 8 6
0
0
0
2 1 11
0
3 9 4 3
0
0
0
2 10 2
2
0
1 0
3
0
2 0 2
0
1
0
8
0
0
0
0
3 6 7 2
0
2 1 0
2 5 3
6
4
8
11
5
4
1
4
9
3
8
13
6
11
16
16
3
4
1
11
Il faut être logué pour pouvoir envoyer une soumission.