Can anyone give an optimal approach to solve the below problem which had been asked in hacker earth hiring challenge?
Problem statement -
You have been given a tree having all nodes colored with either black or white color. You have to count the number of pairs of only black nodes which are having at least one white node in between their path.
Do you have a screenshot or a link ?
Remove the white nodes, for the remaining components add sz_i \choose 2, where sz_i denotes size of i^{th} component. This gives you number of paths with only black nodes. Subtract this value from b \choose 2, where b is number of black nodes.
What is not clear? Just draw some trees and try to understand the formula.
@samarth2017 what do you mean by the size of the component? I try searching on google but didn’t get any relevant definition.
By size of the component, he means the size of connected component. After removing the white nodes, the tree might not be connected and hence would take the form of a graph with several connected components. Just google connected components in a graph for further details. You can use simple dfs to find the size of connected components.
Can you please explain with this example
N=3
color[]={1, 0, 0} // 1 is white 0 is black
M=2
1 2
1 3
Output should be 1
