Dado un Árbol con N vértices y N – 1 arista donde los vértices están numerados de 0 a N – 1 , y un vértice V presente en el árbol. Se da que cada vértice en el árbol tiene asignado un color que es blanco o negro y los colores respectivos de los vértices están representados por una array arr[] . La tarea es encontrar la diferencia máxima entre el número de vértices de color blanco y el número de vértices de color negro de cualquier subárbol posible del árbol dado que contiene el vértice V dado .
Ejemplos:
Input: V = 0, arr[] = {'b', 'w', 'w', 'w', 'b', 'b', 'b', 'b', 'w'} Tree: 0 b / \ / \ 1 w 2 w / / \ / / \ 5 b w 3 4 b | | | | | | 7 b b 6 8 w Output: 2 Explanation: We can take the subtree containing the vertex 0 which contains vertices 0, 1, 2, 3 such that the difference between the number of white and the number of black vertices is maximum which is equal to 2. Input: V = 2, arr[] = {'b', 'b', 'w', 'b'} Tree: 0 b / | \ / | \ 1 2 3 b w b Output: 1
Enfoque: La idea es utilizar el concepto de programación dinámica para resolver este problema.
- En primer lugar, cree un vector para la array de colores y para el color blanco, presione 1 y para el color negro, presione -1.
- Haga una array dp[] para calcular la diferencia máxima posible entre el número de vértices blancos y negros en algún subárbol que contenga el vértice V.
- Ahora, recorra el árbol utilizando el recorrido de búsqueda primero en profundidad y actualice los valores en la array dp[].
- Finalmente, el valor mínimo presente en la array dp[] es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find maximum // difference between count of // black and white vertices in // a path containing vertex V #include <bits/stdc++.h> using namespace std; // Defining the tree class class tree { vector<int> dp; vector<vector<int> > g; vector<int> c; public: // Constructor tree(int n) { dp = vector<int>(n); g = vector<vector<int> >(n); c = vector<int>(n); } // Function for adding edges void addEdge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } // Function to perform DFS // on the given tree void dfs(int v, int p = -1) { dp[v] = c[v]; for (auto i : g[v]) { if (i == p) continue; dfs(i, v); // Returning calculated maximum // difference between white // and black for current vertex dp[v] += max(0, dp[i]); } } // Function that prints the // maximum difference between // white and black vertices void maximumDifference(int v, char color[], int n) { for (int i = 0; i < n; i++) { // Condition for white vertex if (color[i] == 'w') c[i] = 1; // Condition for black vertex else c[i] = -1; } // Calling dfs function for vertex v dfs(v); // Printing maximum difference between // white and black vertices cout << dp[v] << "\n"; } }; // Driver code int main() { tree t(9); t.addEdge(0, 1); t.addEdge(0, 2); t.addEdge(2, 3); t.addEdge(2, 4); t.addEdge(1, 5); t.addEdge(3, 6); t.addEdge(5, 7); t.addEdge(4, 8); int V = 0; char color[] = { 'b', 'w', 'w', 'w', 'b', 'b', 'b', 'b', 'w' }; t.maximumDifference(V, color, 9); return 0; }
Java
// Java program to find maximum // difference between count of // black and white vertices in // a path containing vertex V import java.util.*; // Defining the // tree class class GFG{ static int []dp; static Vector<Integer> []g; static int[] c; // Constructor GFG(int n) { dp = new int[n]; g = new Vector[n]; for (int i = 0; i < g.length; i++) g[i] = new Vector<Integer>(); c = new int[n]; } // Function for adding edges void addEdge(int u, int v) { g[u].add(v); g[v].add(u); } // Function to perform DFS // on the given tree static void dfs(int v, int p) { dp[v] = c[v]; for (int i : g[v]) { if (i == p) continue; dfs(i, v); // Returning calculated maximum // difference between white // and black for current vertex dp[v] += Math.max(0, dp[i]); } } // Function that prints the // maximum difference between // white and black vertices void maximumDifference(int v, char color[], int n) { for (int i = 0; i < n; i++) { // Condition for // white vertex if (color[i] == 'w') c[i] = 1; // Condition for // black vertex else c[i] = -1; } // Calling dfs function // for vertex v dfs(v, -1); // Printing maximum difference // between white and black vertices System.out.print(dp[v] + "\n"); } // Driver code public static void main(String[] args) { GFG t = new GFG(9); t.addEdge(0, 1); t.addEdge(0, 2); t.addEdge(2, 3); t.addEdge(2, 4); t.addEdge(1, 5); t.addEdge(3, 6); t.addEdge(5, 7); t.addEdge(4, 8); int V = 0; char color[] = {'b', 'w', 'w', 'w', 'b', 'b', 'b', 'b', 'w'}; t.maximumDifference(V, color, 9); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to find maximum # difference between count of # black and white vertices in # a path containing vertex V # Function for adding edges def addEdge(g, u, v): g[u].append(v) g[v].append(u) # Function to perform DFS # on the given tree def dfs(v, p, dp, c, g): dp[v] = c[v] for i in g[v]: if i == p: continue dfs(i, v, dp, c, g) # Returning calculated maximum # difference between white # and black for current vertex dp[v] += max(0, dp[i]) # Function that prints the # maximum difference between # white and black vertices def maximumDifference(v, color, n, dp, c, g): for i in range(n): # Condition for white vertex if(color[i] == 'w'): c[i] = 1 # Condition for black vertex else: c[i] = -1 # Calling dfs function for vertex v dfs(v, -1, dp, c, g) # Printing maximum difference between # white and black vertices print(dp[v]) # Driver code n = 9 g = {} dp = [0] * n c = [0] * n for i in range(0, n + 1): g[i] = [] addEdge(g, 0, 1) addEdge(g, 0, 2) addEdge(g, 2, 2) addEdge(g, 2, 4) addEdge(g, 1, 5) addEdge(g, 3, 6) addEdge(g, 5, 7) addEdge(g, 4, 8) V = 0 color = [ 'b', 'w', 'w', 'w', 'b', 'b', 'b', 'b', 'w' ] maximumDifference(V, color, 9, dp, c, g) # This code is contributed by avanitrachhadiya2155
C#
// C# program to find maximum // difference between count of // black and white vertices in // a path containing vertex V using System; using System.Collections.Generic; // Defining the // tree class class GFG{ static int []dp; static List<int> []g; static int[] c; // Constructor GFG(int n) { dp = new int[n]; g = new List<int>[n]; for (int i = 0; i < g.Length; i++) g[i] = new List<int>(); c = new int[n]; } // Function for adding edges void addEdge(int u, int v) { g[u].Add(v); g[v].Add(u); } // Function to perform DFS // on the given tree static void dfs(int v, int p) { dp[v] = c[v]; foreach (int i in g[v]) { if (i == p) continue; dfs(i, v); // Returning calculated maximum // difference between white // and black for current vertex dp[v] += Math.Max(0, dp[i]); } } // Function that prints the // maximum difference between // white and black vertices void maximumDifference(int v, char []color, int n) { for (int i = 0; i < n; i++) { // Condition for // white vertex if (color[i] == 'w') c[i] = 1; // Condition for // black vertex else c[i] = -1; } // Calling dfs function // for vertex v dfs(v, -1); // Printing maximum difference // between white and black vertices Console.Write(dp[v] + "\n"); } // Driver code public static void Main(String[] args) { GFG t = new GFG(9); t.addEdge(0, 1); t.addEdge(0, 2); t.addEdge(2, 3); t.addEdge(2, 4); t.addEdge(1, 5); t.addEdge(3, 6); t.addEdge(5, 7); t.addEdge(4, 8); int V = 0; char []color = {'b', 'w', 'w', 'w', 'b', 'b', 'b', 'b', 'w'}; t.maximumDifference(V, color, 9); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript program to find maximum // difference between count of // black and white vertices in // a path containing vertex V let n = 9; let dp = new Array(n); let g = new Array(n); let c = new Array(n); for (let i = 0; i < g.length; i++) g[i] = []; // Function for adding edges function addEdge(u, v) { g[u].push(v); g[v].push(u); } // Function to perform DFS // on the given tree function dfs(v, p) { dp[v] = c[v]; for (let i = 0; i < g[v].length; i++) { if (g[v][i] == p) continue; dfs(g[v][i], v); // Returning calculated maximum // difference between white // and black for current vertex dp[v] += Math.max(0, dp[g[v][i]]); } } // Function that prints the // maximum difference between // white and black vertices function maximumDifference(v, color, n) { for (let i = 0; i < n; i++) { // Condition for // white vertex if (color[i] == 'w') c[i] = 1; // Condition for // black vertex else c[i] = -1; } // Calling dfs function // for vertex v dfs(v, -1); // Printing maximum difference // between white and black vertices document.write(dp[v] + "</br>"); } addEdge(0, 1); addEdge(0, 2); addEdge(2, 3); addEdge(2, 4); addEdge(1, 5); addEdge(3, 6); addEdge(5, 7); addEdge(4, 8); let V = 0; let color = ['b', 'w', 'w', 'w', 'b', 'b', 'b', 'b', 'w']; maximumDifference(V, color, 9); // This code is contributed by divyeshrabadiya07. </script>
2
Complejidad temporal: O(N) , donde N es el número de vértices del árbol.
Publicación traducida automáticamente
Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA