Subtree with minimum color difference in a 2coloured tree
A tree with N nodes and N1 edges is given with 2 different colours for its nodes.
Find the subtree with minimum colour difference i.e. abs(1colour nodes – 2colour nodes) is minimum.
Examples:
Input : Edges : 1 2 1 3 2 4 3 5 Colours : 1 1 2 2 1 [1based indexing where index denotes the node] Output : 2 Explanation : The subtree {12} and {1235} have color difference of 2. Subtree {12} has two 1colour nodes and zero 2colour nodes. So, color difference is 2. Subtree {1235} has three 1colour nodes and one 2colour nodes. So color diff = 2.
Method 1 : The problem can be solved by checking every possible subtree from every node of the tree. This will take exponential time as we will check for subtrees from every node.
Method 2 : (Efficient) If we observe, we are solving a portion of the tree several times. This produces recurring subproblems. 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 subtree 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 subtree 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 subtree 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 viceversa.
Below is the C++ implementation :

// CPP code to find the subtree with minimum color
// difference in a 2<a href="#">coloured tree</a>
#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 subtree 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
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide