# Boleyn Salary – HackerRank Solution

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

Contents

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

1. Boleyn, employee id 1, represents the root node.
2. Each pair of employee is directly or indirectly connected to one another.
3. 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 ith 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 kth lowest salary among her subordinates. Help them in solving their query.

Note

1. 1stÂ lowest salary is equivalent to lowest salary,Â 2ndÂ lowest means lowest salary which is greater thatÂ 1stÂ lowest salary, and so on.
2. Salary of each employee is different.
3. 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Â ithÂ 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Â kthÂ lowest salary among the subordinates ofÂ v.
For the subsequent queries, we need to find theÂ kthÂ lowest salary of the subordinates ofÂ v+d, whereÂ dÂ is the answer of previous query.

## Constraints

• 1 â‰¤Â NÂ â‰¤ 3*104
• 1 â‰¤Â QÂ â‰¤ 3*104
• 1 â‰¤Â s[i]Â â‰¤ 109,Â iÂ âˆˆÂ [1..N]
• s[i]Â â‰  s[j], 1 â‰¤ i < j â‰¤Â N
• 1 â‰¤Â u, pÂ â‰¤Â N,Â uÂ â‰ Â p
• -NÂ â‰¤Â dÂ â‰¤Â N
• ForÂ 1stÂ query, 1 â‰¤Â 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Â 1stÂ 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)Â .Â 8thÂ employee has theÂ 5thÂ lowest salary among the subordinate ofÂ 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).Â 6thÂ employee has the most, and only, lowest salary.
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
(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)

(0 until q).foreach(_ => {
val v = sc.nextInt
val k = sc.nextInt

val id = answer + v