Ninja and Employees

Easy
0/40
Average time to solve is 20m
1 upvote
Asked in company
Blue Yonder Private Limited

Problem statement

Ninja is managing a company of Employees. There are N employees in the company and their unique IDs are labeled from 0 to N-1. All the employees are arranged in a tree-like structure according to their rank. Each employee has been assigned some importance point. Given an integer X , Ninja wants to know the total of importance points of Employee having ID as ‘X’ and all its subordinates.Can you help Ninja to find the total importance points quickly?

You are given a tree having ‘N’ nodes and ‘N’-1 edges. And an array ‘POINTS’ where POINTS[i] denotes the importance points of employee with ID as i and an integer ‘X’ is given. Print the sum of importance points of employee ‘X’ and all its subordinates.

For Example 
If the given tree:
And POINTS = [3,5,1,4] and X = 2

altImage

The answer will be 5 (Points of 2 + Points of 3).

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of kingdoms.

The next ‘N’-1 lines of each test case contain two integers representing an edge between the given indices.
The next line contains the ‘POINTS’ array.
The next line contains a single integer ‘X’.
Output Format: 
For each test case, print the sum of importance points of Employee ‘X’ and all its subordinates.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^6.
1 <= POINTS[i] <= 1000
0 <= X < N. 

Time limit: 1 sec
Sample Input 1:
2
4
0 1
0 2
2 3
3 5 1 4
2
5
0 1
1 2
1 3
1 4
1 2 3 4 5
0
Sample Output 1:
5
15
Explanation of sample input 1:
For the first test case,

altImage The subordinates of Node 2 is 3 only.So the answer will be POINTS[2] + POINTS[3]= 5. Hence,the answer is 5.

For the second test case:

atlimage

The subordinates of Node 0 are Node 1, Node 2, Node 3, and Node 4. So the answer will be the sum of points of all these nodes.Answer will be (POINTS[0] + POINTS[1] + POINTS[2] + POINTS[3] +POINTS[4]  )= 15.
Hence, the answer is 15.
Sample Input 2:
2
6
0 1
0 5
1 2
1 3
3 4
7 3 3 10 10 9 
2
9
0 1 
0 4
0 7
1 2  
2 3
3 6
4 5
4 8
1 2 8 5 5 6 2 3 4 
1
Sample Output 2:
3 
17
Hint

Try to travel the subtree of ‘X’ recursively.

Approaches (2)
Depth First Search.

In this approach, we will travel to all the nodes in a subtree of ‘X’ and return the sum of points of all subordinates.We will define a recursive function DFS(‘CUR’,’TREE’,’POINTS’) which will return the answer for the Node having ID as ‘X’ and we will make the recursive call for all of his direct subordinates.

At last,we will return the answer for DFS(X, TREE, POINTS).

Algorithm:

  • Defining DFS(‘CUR’,’ TREE’,’ POINTS’) function that will return the sum of points for all subordinates of ‘CUR’ including ‘CUR’. ’POINTS’ is the given points array and ‘TREE’ is the tree stored in an adjacency list manner.
    • Set ‘ANS’ as POINTS[CUR].
    • For ‘NODE’  in TREE[CUR]:
      • Set ‘ANS’ as ‘ANS’ + DFS(NODE,TREE,POINTS).
    • Return ‘ANS’.


 

  • Define ‘TREE’ to store this tree in an adjacency list manner.
  • For i in range 0 to N-2:
    • Append ‘EDGES’[i][1] to TREE[‘EDGES[i][0]’].


 

  • Declare the ‘ANS’ variable to store the final answer.
  • Set ‘ANS’ as DFS(X, TREE, POINTS).
  • Return ANS.
Time Complexity

O(N), where ‘N’ is the number of employees.

 

In this approach, we are calling DFS() function for each node X and  the time complexity of DFS function is O(V+E) where V is the number of vertices and E is the number of edges.

In case of Tree, the time complexity is O(N + N -1). Hence, the overall time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the number of employees.

 

In this approach, we are calling the DFS function, which will make recursive calls and at the worst case, N calls will be made. So O(N) space will be consumed in stack memory and we are also storing TREE which also takes O(N) space. So, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Ninja and Employees
Full screen
Console