Given a Tree with N vertices and N – 1 edge where the vertices are numbered from 0 to N – 1, and a vertex V present in the tree. It is given that each vertex in the tree has a color assigned to it which is either white or black and the respective colors of the vertices are represented by an array arr[]. The task is to find the maximum difference between the number of white-colored vertices and the number of black colored vertices from any possible subtree from the given tree that contains the given vertex V.
Examples:
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
Approach: The idea is to use the concept of dynamic programming to solve this problem.
- Firstly, make a vector for color array and for white color, push 1 and for black color, push -1.
- Make an array dp[] to calculate the maximum possible difference between the number of white and black vertices in some subtree containing the vertex V.
- Now, traverse through the tree using depth first search traversal and update the values in dp[] array.
- Finally, the minimum value present in the dp[] array is the required answer.
Below is the implementation of the above approach:
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 classclass 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 codeint 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 Vimport java.util.*;// Defining the // tree classclass GFG{ static int []dp;static Vector<Integer> []g;static int[] c;// ConstructorGFG(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 edgesvoid addEdge(int u, int v){ g[u].add(v); g[v].add(u);}// Function to perform DFS// on the given treestatic 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 verticesvoid 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 codepublic 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 edgesdef addEdge(g, u, v): g[u].append(v) g[v].append(u)# Function to perform DFS # on the given treedef 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 coden = 9g = {}dp = [0] * nc = [0] * nfor 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 = 0color = [ '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 Vusing System;using System.Collections.Generic;// Defining the // tree classclass GFG{ static int []dp;static List<int> []g;static int[] c;// ConstructorGFG(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 edgesvoid addEdge(int u, int v){ g[u].Add(v); g[v].Add(u);}// Function to perform DFS// on the given treestatic 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 verticesvoid 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 codepublic 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> |
Output:
2
Time Complexity: O(N), where N is the number of vertices in the tree.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
