Last Updated: 12 Dec, 2021
Ninja and Employees
Easy
Asked in company
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
The answer will be 5 (Points of 2 + Points of 3).
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
Approaches
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.
In this approach, we will traverse the subtree of ‘X’ using breadth first search .We will use a queue to store the traverse and will maintain a variable ‘ANS’ that will store the sum of points.
Algorithm:
- 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 0.
- Declare a queue ‘Q’ to traverse the subtree.
- Insert ‘X’ into Q.
- While length of ‘Q’ is greater than 0:
- Set ‘CUR’ as front element of ‘Q’.
- Remove the front element from ‘Q’.
- Set ‘ANS’ as ‘ANS’ + POINTS[CUR].
- For i in TREE[CUR]:
- Insert i into Queue Q.
- Return ANS.