I found an interesting problem on the tree in google's online assessment. You have been given a Tree consisting of N nodes, and an array V of length N presents the value of ith Node — V[i]. You have to find the number of distinct paths of length greater than one where the value of the starting node equals the value of the ending node. And all the node values between starting and ending nodes should be less than or equal to the value of starting node.
constraints:
1<= N <= 100000
Sample input:
N = 5
edges = [{1,2}, {1,3}, {3, 4}, {3, 5}]
V = [2, 3, 1, 2, 3]
Output:
2
explanation:
path = 1-3-4
path = 2-1-3-5
I was able to come up with a solution with a time complexity of O(N^3). I was wondering how to solve this efficiently.
Hint: disjoint set union.
Start with a set of $$$N$$$ nodes, without any edges added. At this point, each node is a connected component by itself.
Let $$$V'$$$ be the set of values ($$$V$$$ without duplicates). For each $$$v \in V'$$$ in ascending order, add edges with one endpoint with value $$$v$$$ and another endpoint with value $$$\leq v$$$. Maintain the connected components that are formed during this procedure using disjoint set data structure. After the edges are added, if in a component $$$C$$$ there are $$$k$$$ nodes with value $$$v$$$, add $$$k(k - 1) / 2$$$ to the answer — this counts the number of paths with two endpoints with value $$$v$$$ in $$$C$$$.
In the end, we will have counted the number of distinct paths with two endpoints with equal values, with the values of the intermediate nodes not exceeding the value of the endpoints. What remains is to subtract the number of paths of length 1 with endpoints with equal values. But this is trivial — just subtract the number of corresponding edges.
With careful implementation, the running time should be $$$O(N log N)$$$ because of sorting.
Consider a node $$$ u $$$ , find the farthest ancestor $$$ p $$$ such that the path from $$$ u $$$ to $$$ p $$$ contains values $$$ \lt =A[u] $$$. Compute this for all nodes $$$ u $$$ in the tree . Now for any pair $$$(u,v)$$$ to form special path obviously $$$ A[u] == A[v] $$$ and they must have this common farthest ancestor described above (You can check all cases when $$$(u,v)$$$ form the answer they have same common farthest ancestor). Now for each node assuming it to be the farthest ancestor compute the count of nodes having same value , let it be $$$ C $$$ , increment the answer by $$$ C*(C-1)/2 $$$. Attaching the implementation of above approach : https://pastebin.com/TGcDtBpK `