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

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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.push_back(2); ` `    ``tree.push_back(1); ` ` `  `    ``tree.push_back(3); ` `    ``tree.push_back(1); ` ` `  `    ``tree.push_back(4); ` `    ``tree.push_back(2); ` ` `  `    ``tree.push_back(5); ` `    ``tree.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
```