2872. Nombre maximum de composants K-divisibles

2872. Nombre maximum de composants K-divisibles

Difficulté : Difficile

Sujets :Arbre,Recherche en profondeur

Il existe un arbre non orienté avecnnœuds étiquetés à partir de0àn-1. On vous donne l'entiernet un tableau d'entiers 2Dbordsde longueurn-1, oùbords[i] = [ai, bi]indique qu'il y a un bord entre les nœudsaietbidans l'arbre.

Vous recevez également un tableau d’entiers indexés à 0valeursde longueurn, oùvaleurs[i]est la valeur associée auavecnœud et un entierk.

Une division valide de l'arbre est obtenue en supprimant tout ensemble d'arêtes, éventuellement vides, de l'arbre de telle sorte que les composants résultants aient tous des valeurs divisibles park, où la valeur d'un composant connecté est la somme des valeurs de ses nœuds.

Renvoie le nombre maximum de composants dans toute division valide.

Exemple 1 :

• Entrée : n = 5, bords = [[0,2],[1,2],[1,3],[2,4]], valeurs = [1,8,1,4,4], k = 6
• Sortie : 2
• Explication : Nous supprimons le nœud de connexion de bord 1 avec 2. La division résultante est valide car :
  • La valeur du composant contenant les nœuds 1 et 3 est valeurs[1] + valeurs[3] = 12.
  • La valeur du composant contenant les nœuds 0, 2 et 4 est valeurs[0] + valeurs[2] + valeurs[4] = 6.
  • On peut montrer qu’aucune autre division valide n’a plus de 2 composants connectés.

Exemple 2 :

• Entrée : n = 7, bords = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], valeurs = [3 ,0,6,1,5,2,1], k = 3
• Sortie : 3
• Explication : Nous supprimons le nœud de connexion de bord 0 avec 2 et le nœud de connexion de bord 0 avec 1. La divi...
  [Courte citation de 8% de l'article original]