Similar Pair : Challenge | 101 Hack | HackerRank
You are given a tree where each node is labeled from 1, 2, …, n. How many similar pairs(S) are there in this tree?
A pair (A,B) is a similar pair iff
node A is the ancestor of node B
abs(A - B) <= T.
Now as we traverse each node we will store it in a data stucture to keep track of all the ancestor for the next node but before that get the number of its own ancestors in the range [presentNode-T, PresentNode+T] and add it to the total pairs.
Data Structure
Now we need a data structure which can:
1. Insert a node as we travese the tree.
2. Remove a node as we return back.
3. Give number of nodes within the range [presentNode-T, PresentNode+T] which it have stored.
All of the above 3 operation needs to be done in log(N) time because N<=10^5 so we can take up our complexity to O(N log(N)). Binary Index Tree (BIT) is the a data structure which fulfills all of the above condition (There are other data structure like Segment Treewhich can also be used).
We can do the above 3 operation by initialize all the index valve of BIT to 0 and then:
1. Insert a node by updating index of that node to 1
2. Remove a node by updating index of that node to 0
3. Get number of similar pair ancestor of that node by quary for sum of range in [presentNode-T, PresentNode+T]
If you are not familiar with BIT / Segement tree refer: BIT Tutorial / Segment Tree Tutorial
Use it to solve the problem in O(N log(N)). The DFS pseudo code will look like:
DFS(int node)
similar_pair += bit_range_sum(max(1,node-t),min(n,node+t));
bit_update(node,1);
for(int i=0;i<al[node].size();i++)
dfs(al[node][i]);
bit_update(node,0);