Maximale Anzahl K-teilbarer Komponenten

2872. Maximale Anzahl K-teilbarer Komponenten

Schwierigkeit:Schwer

Themen:Baum, Tiefensuche

Es gibt einen ungerichteten Baum mit n Knoten, die von 0 bis n - 1 beschriftet sind. Sie erhalten die Ganzzahl n und ein 2D-Ganzzahlarray mit Kanten der Länge n - 1, wobei Kanten[i] = [a_i, b_i] zeigt an, dass es eine Kante zwischen den Knoten a_i und gibt b_iim Baum.

Sie erhalten außerdem ein 0-indiziertes ganzzahliges Array mit Werten der Länge n, wobei „values[i]“ der Wert ist, der dem i^ten Knoten zugeordnet ist, und eine ganze Zahl k.

Eine gültige Aufteilung des Baums wird erhalten, indem alle Kantensätze (möglicherweise leer) aus dem Baum entfernt werden, sodass die resultierenden Komponenten alle Werte haben, die durch k teilbar sind, wobei der Wert einer verbundenen Komponente ist die Summe der Werte ihrer Knoten.

Geben Sie die maximale Anzahl von Komponenten in jeder gültigen Aufteilung zurück.

Beispiel 1:

• Eingabe: n = 5, Kanten = [[0,2],[1,2],[1,3],[2,4]], Werte = [1,8,1,4 ,4], k = 6
• Ausgabe: 2
• Erklärung: Wir entfernen die Kante, die Knoten 1 mit 2 verbindet. Die resultierende Aufteilung ist gültig, weil:
  • Der Wert der Komponente, die die Knoten 1 und 3 enthält, ist Werte[1] Werte[3] = 12.
  • Der Wert der Komponente, die die Knoten 0, 2 und 4 enthält, ist Werte[0] Werte[2] Werte[4] = 6.
  • Es kann gezeigt werden, dass kein anderer gültiger Split mehr als 2 verbundene Komponenten hat.

Beispiel 2:

• Eingabe: n = 7, Kanten = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6] ], Werte = [3,0,6,1,5,2,1], k = 3
• Ausgabe: 3
• Erklärung: Wir entfernen die Kante, die Knoten 0 mit 2 verbindet, und die Kante, die Knoten 0 mit 1 verbindet. Die resultierende Aufteilung ist gültig, weil:
  • Der Wert der Komponente, die Knoten 0 enthält, ist Werte[0] = 3.
  • Der Wert der Komponente, die die Knoten 2, 5 und 6 enthält, ist Werte[2] Werte[5] Werte[6] = 9.
  • Der Wert der Komponente, die die Knoten 1, 3 und 4 enthält, ist Werte[1] Werte[3] Werte[4] = 6.
  • Es kann gezeigt werden, dass keine andere gültige Aufteilung mehr als 3 verbundene Komponenten hat.

Einschränkungen:

• 1 <= n <= 3 * 10⁴
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• values.length == n
• 0 <= Werte[i] <= 10⁹
• 1 <= k <= 10⁹
• Die Summe der Werte ist durch k teilbar.
• Die Eingabe wird so generiert, dass Kanten einen gültigen Baum darstellen.

Hinweis:

1. Wurzeln Sie den Baum am Knoten 0.
2. Wenn ein Blattknoten nicht durch k teilbar ist, muss er sich in derselben Komponente wie sein übergeordneter Knoten befinden, also verschmelzen wir ihn mit seinem übergeordneten Knoten.
3. Wenn ein Blattknoten durch k teilbar ist, besteht er aus seinen eigenen Komponenten, sodass wir ihn von seinem übergeordneten Knoten trennen.
4. In jedem Schritt schneiden wir entweder einen Blattknoten ab oder führen einen Blattknoten zusammen. Die Anzahl der Knoten im Baum verringert sich um eins. Wiederholen Sie diesen Vorgang, bis nur noch ein Knoten übrig ist.

Lösung:

Wir können einen DFS-Ansatz (Depth-First Search) implementieren, um den Baum zu erkunden, die Werte von Komponenten zu verfolgen und die maximale Anzahl gültiger Teilungen zu finden.

Kernpunkte:

• Baumstruktur: Wir arbeiten mit einem ungerichteten Baum, bei dem jedem Knoten ein Wert zugeordnet ist. Wir müssen die maximale Anzahl verbundener Komponenten ermitteln, die wir erhalten können, indem wir den Baum so aufteilen, dass die Summe der Werte jeder Komponente durch k teilbar ist.
• DFS-Durchquerung: Wir verwenden Depth-First Search (DFS), um den Baum zu durchqueren und die Teilbaumsummen zu berechnen.
• Teilbarkeitsprüfung: Wenn nach der Berechnung der Summe eines Teilbaums diese durch k teilbar ist, bedeutet dies, dass der Teilbaum als eigenständige, gültige Komponente betrachtet werden kann.
• Kantenentfernung: Durch das Entfernen von Kanten, die Knoten verbinden, deren Teilbaumsummen nicht durch k teilbar sind, können wir die Anzahl gültiger Komponenten maximieren.

Ansatz:

1. Baumdarstellung: Wandeln Sie die Kantenliste in eine Adjazenzliste um, um den Baum darzustellen.
2. DFS-Traversal: Beginnen Sie bei Knoten 0 und berechnen Sie rekursiv die Summe der Werte in jedem Teilbaum. Wenn die Summe durch k teilbar ist, können wir diesen Teilbaum von seinem übergeordneten Baum abschneiden und so effektiv eine gültige Komponente bilden.
3. Globale Anzahl: Führen Sie einen globalen Zähler (Ergebnis), der die Anzahl der gültigen Komponenten verfolgt, die durch Schnittkanten gebildet werden.
4. Endprüfung: Stellen Sie am Ende des DFS-Durchlaufs sicher, dass die gesamte Teilbaumsumme der Wurzel, wenn sie durch k teilbar ist, als gültige Komponente gilt.

Planen:

1. Eingabeanalyse: Konvertieren Sie die Eingabe in eine verwendbare Form. Erstellen Sie insbesondere eine Adjazenzlistendarstellung für den Baum.
2. DFS-Funktion: Schreiben Sie eine rekursive Funktion dfs(node), die die Summe der Werte im Teilbaum berechnet, der beim Knoten verwurzelt ist. Wenn diese Summe durch k teilbar ist, erhöhen Sie den Ergebniszähler und „schneiden“ Sie die Kante ab, indem Sie 0 zurückgeben, um eine Rückverschmelzung mit der übergeordneten Summe zu verhindern.
3. Starten Sie DFS von Root: Rufen Sie dfs(0) auf und überprüfen Sie dann den Endwert des Ergebnisses.

Lösungsschritte:

1. Erstellen Sie den Baum: Wandeln Sie die Kantenliste zur einfacheren Durchquerung in eine Adjazenzliste um.
2. Besuchtes Array initialisieren:Verwenden Sie ein besuchtes Array, um sicherzustellen, dass wir Knoten nicht erneut besuchen.
3. DFS-Durchquerung: Führen Sie DFS ab Knoten 0 durch. Berechnen Sie für jeden Knoten die Summe der Werte seines Teilbaums.
4. Teilbarkeit prüfen: Wenn die Summe eines Teilbaums durch k teilbar ist, erhöhen Sie das Ergebnis und setzen Sie die Teilbaumsumme auf 0 zurück.
5. Abschließende Komponentenprüfung:Überprüfen Sie nach dem DFS-Durchlauf, ob der gesamte Baum (Wurzel am Knoten 0) eine durch k teilbare Summe hat, und berücksichtigen Sie diese bei Bedarf als separate Komponente.

Lassen Sie uns diese Lösung in PHP implementieren: 2872. Maximale Anzahl K-teilbarer Komponenten

  
  
  Erläuterung:




Baumkonstruktion: Wir erstellen eine Adjazenzliste, um die Baumstruktur darzustellen. Jede Kante verbindet zwei Knoten und wir verwenden diese Adjazenzliste, um den Baum zu durchlaufen.

DFS-Traversal: Die DFS-Funktion berechnet rekursiv die Summe des Teilbaums, der an jedem Knoten verwurzelt ist. Wenn die Summe des Teilbaums durch k teilbar ist, erhöhen wir das Ergebnis und betrachten den Teilbaum als separate gültige Komponente.

Teilbaumsumme zurückgeben: Für jeden Knoten gibt die DFS-Funktion die Summe der Werte für seinen Teilbaum zurück. Wenn ein Teilbaum durch k teilbar ist, „schneiden“ wir die Kante effektiv ab, indem wir eine Summe von 0 zurückgeben, wodurch eine weitere Verschmelzung mit dem übergeordneten Knoten verhindert wird.

Endprüfung: Am Ende des DFS stellen wir sicher, dass die Summe des gesamten Baums, wenn sie durch k teilbar ist, als gültige Komponente gilt.



  
  
  Beispielhafte Vorgehensweise:


Beispiel 1:

Eingabe:



n = 5, Kanten = [[0,2],[1,2],[1,3],[2,4]], Werte = [1,8,1,4,4], k = 6. 


DFS beginnt bei Knoten 0:


Knoten 0: Teilbaumsumme = 1
Knoten 2: Teilbaumsumme = 1 1 4 = 6 (teilbar durch 6, damit wir diese Kante abschneiden können)
Knoten 1: Teilbaumsumme = 8 4 = 12 (teilbar durch 6, diese Kante abschneiden)
Endgültige Anzahl der Komponenten = 2.


Beispiel 2:

Eingabe:



n = 7, Kanten = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], Werte = [3,0 ,6,1,5,2,1], k = 3.


DFS beginnt bei Knoten 0:


Knoten 0: Teilbaumsumme = 3
Knoten 2: Teilbaumsumme = 6 2 1 = 9 (teilbar durch 3, diese Kante abschneiden)
Knoten 1: Teilbaumsumme = 0 5 = 5 (nicht durch 3 teilbar, diese Summe zusammenführen)
Endgültige Anzahl der Komponenten = 3.



  
  
  Zeitkomplexität:




DFS-Zeitkomplexität: O(n), wobei n die Anzahl der Knoten ist. Wir besuchen jeden Knoten einmal und führen an jedem Knoten zeitkonstante Operationen durch.

Raumkomplexität: O(n) für die Adjazenzliste, das besuchte Array und den Rekursionsstapel.


Daher beträgt die gesamte Zeit- und Raumkomplexität O(n), was diesen Ansatz für die gegebenen Problembeschränkungen effizient macht.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonMaximale Anzahl K-teilbarer Komponenten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!