We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Similar Pair

Similar Pair

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

A pair of nodes, , is a similar pair if the following conditions are true:

  1. node is the ancestor of node

Given a tree where each node is labeled from to , find the number of similar pairs in the tree.

For example, given the following tree:

image

We have the following pairs of ancestors and dependents:

Pair	abs(a-b)	Pair	abs(a-b)
1,2	1		3,4	1
1,3	2		3,5	2
1,4	3		3,6	3
1,5	4
1,6	5

If for example, we have pairs that are similar, where .

Function Description

Complete the similarPair function in the editor below. It should return an integer that represents the number of pairs meeting the criteria.

similarPair has the following parameter(s):

  • n: an integer that represents the number of nodes
  • k: an integer
  • edges: a two dimensional array where each element consists of two integers that represent connected node numbers

Input Format

The first line contains two space-separated integers and , the number of nodes and the similarity threshold.
Each of the next lines contains two space-separated integers defining an edge connecting nodes and , where node is the parent to node .

Constraints

Output Format

Print a single integer denoting the number of similar pairs in the tree.

Sample Input

5 2
3 2
3 1
1 4
1 5

Sample Output

4

Explanation

image
The similar pairs are , , , and , so we print as our answer.
Observe that and are not similar pairs because they do not satisfy for .

Author

idlecool

Difficulty

Advanced

Max Score

70

Submitted By

5800

Need Help?


View discussions
View editorial
View top submissions
RESOURCES

  • Depth First Search
  • Binary Indexed Tree

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy