Tutorialspoint.dev

Sub-tree with minimum color difference in a 2-coloured tree

A tree with N nodes and N-1 edges is given with 2 different colours for its nodes.
Find the sub-tree with minimum colour difference i.e. abs(1-colour nodes – 2-colour nodes) is minimum.

Examples:

Input : 
Edges : 1 2
        1 3
        2 4
        3 5
Colours : 1 1 2 2 1 [1-based indexing where 
                    index denotes the node]
Output : 2
Explanation : The sub-tree {1-2} and {1-2-3-5}
have color difference of 2. Sub-tree {1-2} has two
1-colour nodes and zero 2-colour nodes. So, color 
difference is 2. Sub-tree {1-2-3-5} has three 1-colour
nodes and one 2-colour nodes. So color diff = 2.


Method 1 : The problem can be solved by checking every possible sub-tree from every node of the tree. This will take exponential time as we will check for sub-trees from every node.

Method 2 : (Efficient) If we observe, we are solving a portion of the tree several times. This produces recurring sub-problems. We can use Dynamic Programming approach to get the minimum color difference in one traversal. To make things simpler, we can have color values as 1 and -1. Now, if we have a sub-tree with both colored nodes equal, our sum of colors will be 0. To get the minimum difference, we should have maximum negative sum or maximum positive sum.

  • Case 1 When we need to have a sub-tree with maximum sum : We take a node if its value > 0, i.e. sum(parent) += max(0, sum(child))
  • Case 2 When we need to have a sub-tree with minimum sum(or max negative sum) : We take a node if its value < 0, i.e. sum(parent) += min(0, sum(child))

To get the minimum sum, we can interchange the colors of nodes, i.e. -1 becomes 1 and vice-versa.

Below is the C++ implementation :

// CPP code to find the sub-tree with minimum color
// difference in a 2-coloured tree
#include <bits/stdc++.h>
using namespace std;
  
// Tree traversal to compute minimum difference
void dfs(int node, int parent, vector<int> tree[], 
                    int colour[], int answer[])
{
    // Initial min difference is the color of node
    answer[node] = colour[node];
  
    // Traversing its children
    for (auto u : tree[node]) {
  
        // Not traversing the parent
        if (u == parent)
            continue;
  
        dfs(u, node, tree, colour, answer);
  
        // If the child is adding positively to
        // difference, we include it in the answer
        // Otherwise, we leave the sub-tree and 
        // include 0 (nothing) in the answer
        answer[node] += max(answer[u], 0);
    }
}
  
int maxDiff(vector<int> tree[], int colour[], int N)
{
       int answer[N + 1];
       memset(answer, 0, sizeof(answer));
  
    // DFS for colour difference : 1colour - 2colour
    dfs(1, 0, tree, colour, answer);
  
    // Minimum colour difference is maximum answer value
    int high = 0;
    for (int i = 1; i <= N; i++) {
        high = max(high, answer[i]);
  
        // Clearing the current value
        // to check for colour2 as well
        answer[i] = 0;
    }
  
    // Interchanging the colours
    for (int i = 1; i <= N; i++) {
        if (colour[i] == -1)
            colour[i] = 1;
        else
            colour[i] = -1;
    }
  
    // DFS for colour difference : 2colour - 1colour
    dfs(1, 0, tree, colour, answer);
  
    // Checking if colour2 makes the minimum colour 
    // difference
    for (int i = 1; i < N; i++)
        high = max(high, answer[i]);
          
    return high;
}
  
// Driver code
int main()
{
    // Nodes
    int N = 5;
  
    // Adjacency list representation
    vector<int> tree[N + 1];
  
    // Edges
    tree[1].push_back(2);
    tree[2].push_back(1);
  
    tree[1].push_back(3);
    tree[3].push_back(1);
  
    tree[2].push_back(4);
    tree[4].push_back(2);
  
    tree[3].push_back(5);
    tree[5].push_back(3);
  
    // Index represent the colour of that node
    // There is no Node 0, so we start from 
    // index 1 to N
    int colour[] = { 0, 1, 1, -1, -1, 1 };
  
    // Printing the result
    cout << maxDiff(tree,  colour,  N);
      
    return 0;
}

Output:

2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter