- Practice
- Algorithms
- Search
- Similar Pair

# Similar Pair

# Similar Pair

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

- 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:

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**

The similar pairs are , , , and , so we print as our answer.

Observe that and are *not* similar pairs because they do not satisfy for .