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 :2Explanation :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.

## leave a comment

## 0 Comments