Maximum difference of count of black and white vertices in a path containing vertex V

0 0 7 minutes read

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 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>

Output:

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 zambiatek!