In this post, we will solve **Boleyn Salary HackerRank Solution**. This problem **(Boleyn Salary)** is a part of **HackerRank Functional Programming** series.

**Task**

Boleyn Su runs a company called Acme. There are *N* employees in the company, and each one of them is represented by a unique employee id whose range lies in *[1, N]*. Being the head of company, Boleyn’s employee id is *1*.

Each employee, except Boleyn, has exactly one direct superior. This means that the hierarchial structure of the company is like a tree, where

- Boleyn, employee id 1, represents the root node.
- Each pair of employee is directly or indirectly connected to one another.
- There is no cycle.

Let’s represent the salary by the array *s = {s[1], s[2], s[3]…, s[N]}*, where *s[i]* is the salary of the *i ^{th}* employee. Salary structure in the company is non-uniform. Even a subordinate may get a higher salary than her superior. Some of the employees in Acme are curious about who gets the

*k*lowest salary

^{th}*among her subordinates*. Help them in solving their query.

**Note**

*1*lowest salary is equivalent to lowest salary,^{st}*2*lowest means lowest salary which is greater that^{nd}*1*lowest salary, and so on.^{st}- Salary of each employee is different.
- It is not necessary that the people who are placed higher on hierarchy will have a greater salary than their subordinates.

**Input Format**

The first line contains two space separated integers, *N Q*, where *N* is the number of employees in Acme, and *Q* is the number of queries.

Then follows *N-1* lines. Each of these lines contain two space separated integers, *u p*, where *p* is the superior of *u*. *u* and *p* are employees id.

In the next line there are *N* space separated integers, *s[1] s[2] … s[n]*, where *s[i]*, *i ∈ [1..N]*, is the salary of *i ^{th}* employee.

Then,

*Q*queries follow. Each query contains two space separated integers,

*v k*. See output format for it’s definition.

**Output Format**

For the first query, print the id of employee who has the *k ^{th}* lowest salary among the subordinates of

*v*.

For the subsequent queries, we need to find the

*k*lowest salary of the subordinates of

^{th}*v+d*, where

*d*is the answer of previous query.

**Constraints**

- 1 ≤
*N*≤ 3*10^{4} - 1 ≤
*Q*≤ 3*10^{4} - 1 ≤
*s[i]*≤ 10^{9},*i*∈*[1..N]* *s[i]*≠ s[j], 1 ≤ i < j ≤*N*- 1 ≤
*u, p*≤*N*,*u*≠*p* *-N*≤*d*≤*N*- For
*1*query, 1 ≤^{st}*v*≤*N* - For later queries, 1 ≤
*v+d*≤*N* - For each query, 1 ≤
*K*≤ Number_of_subordinates

**Sample Input**

```
8 7
2 1
3 2
4 2
7 4
8 4
5 1
6 5
70 40 60 80 10 20 30 50
2 1
-6 5
-4 1
-5 3
2 1
-5 4
2 2
```

**Sample Output**

```
7
8
7
3
6
2
8
```

**Explanation**

Tree structure will be

```
1(70)
/ \
/ \
2(40) 5(10)
/ \ \
/ \ \
3(60) 4(80) 6(20)
/ \
/ \
7(30) 8(50)
```

*Query #1* `Node = 2`

, `k = 1`

: Subordinates, in increasing order of salary, are *(7, 30), (8, 50), (3, 60), (4, 80)*. So employee *7* has the *1 ^{st}* lowest salary among the subordinates of

*2*.

*Query #2*

`Node = -6+7 = 1`

, `k = 5`

: Subordinates are *(5, 10), (6, 20), (7, 30), (2, 40), (8, 50), (3, 60), (4, 80)*.

*8*employee has the

^{th}*5*lowest salary among the subordinate of

^{th}*1*.

*Query #3*

`Node = -4+8 = 4`

, `k = 1`

: Subordinates are *(7, 30), (8, 50)*. Similarly 7 is the answer of this query.

*Query #4*

`Node = -5+7 = 2`

, `k = 3`

: Subordinates are *(7, 30), (8, 50), (3, 60), (4, 80)*. Similarly 3 is the answer for this query.

*Query #5*

`Node = 2+3 = 5`

, `k = 1`

: Subordinates are *(6, 20)*.

*6*employee has the most, and only, lowest salary.

^{th}*Query #6*

`Node = -5+6 = 1`

, `k = 4`

: Subordinates are *(5, 10), (6, 20), (7, 30), (2, 40), (8, 50), (3, 60), (4, 80)*. 2 is answer of this query.

*Query #7*

`Node = 2+2 = 4`

, `k = 2`

: Subordinates are *(7, 30), (8, 50)*. Employee

*8*has the second lowest salaries among the subordinates of 4.

**Solution – Boleyn Salary – HackerRank Solution**

**Scala**

import java.util.Scanner import scala.collection.immutable.TreeMap object Solution { def main(args: Array[String]): Unit = { val sc = new Scanner(System.in) val n = sc.nextInt val q = sc.nextInt val links = (0 until n - 1).map(_ => (sc.nextInt, sc.nextInt)) .groupBy(_._2) .map { case (key, list) => key -> list.map(_._1) } val salaries = (0 until n).map(_ => sc.nextInt) case class Node(index: Int, count: Int, children: Seq[Node], data: TreeMap[Int, Int]) val nodes = Array.ofDim[Node](n + 1) def create(index: Int): Node = { val children = links.get(index) match { case None => Nil case Some(v) => v.map(create) } val sortedChildren = children.sortBy(-_.count) val data = if (children.isEmpty) TreeMap[Int, Int]() else sortedChildren.tail.foldLeft(sortedChildren.head.data + (salaries(sortedChildren.head.index - 1) -> sortedChildren.head.index))( (acc, c) => acc ++ c.data + (salaries(c.index - 1) -> c.index) ) val res = Node(index, children.map(_.count).sum, children, data) nodes(index) = res res } create(1) var answer = 0 (0 until q).foreach(_ => { val v = sc.nextInt val k = sc.nextInt val id = answer + v answer = nodes(id).data.drop(k - 1).values.head println(answer) }) } }

**Note:** This problem **(Boleyn Salary)** is generated by **HackerRank** but the solution is provided by** CodingBroz**. This tutorial is only for **Educational** and **Learning** purpose.