Diferencia máxima de recuento de vértices blancos y negros en una ruta que contiene el vértice V

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

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