Directi Interview Question for Software Developers
- 0of 0 votes
AnswersYou are given a rooted tree. The tree is not necessarily binary. The tree contains N nodes, labeled 1 to N. You are given the tree in the form of an array P[1..N] of size N. P[i] denotes label of the parent of node labeled i. For clarity, you may assume that the tree satisfies the following conditions.
- evostorm96 November 15, 2017 in India
The root of the tree is labeled 1. Hence P[1] is set to 0.
The parent of node T will always have a label less than T. Hence P[i] < i will always be true.
All nodes contain a mutable value (or, more simply, a variable), which is initially set to 0.
You are asked to perform several operations of the following type
ADD X Y: add Y to the value at node X.
ADDUP X Y: add Y to the value at node X. Then, add Y to the value at P[X] (i.e. the parent of X). The, add Y to the value at P[P[X]] (i.e. the parent of P[X]).. and so on, till you add Y to the value at root.
After you have performed all the given operations, you are asked to answer several queries of the following type
VAL X: print the value at node X.
VALTREE X: print the sum of values at all nodes in the subtree rooted at X (including X).
Input
The first line of input contains the number T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains the numbers N, M and Q respectively (separated by single space character). N depicts the number of nodes. M depicts the number of operations you must perform. Q depicts the number of queries you must answer.
The next N lines contain a number each, depicting the array P[1..N]. Of course the number on the first such line is always 0.
The next M lines contain description of the respective operation. An operation will be either "ADD X Y" or "ADDUP X Y" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the operations.
After the operations, the next Q lines contain description of the queries. A query will be either "VAL X" or "VALTREE X" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the queries.
Output
Print the result of each query on a line by itself. Since the answer for some queries may be too large, please print the result modulo 1,000,000,007. Do not print any blank lines between test cases.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 50000
1 ≤ M ≤ 50000
1 ≤ Q ≤ 50000
1 ≤ X ≤ N
1 ≤ Y ≤ 50000
The input file will be smaller than 2 MB.
Sample Input
2
5 5 3
0
1
1
1
3
ADD 1 10
ADD 2 20
ADD 3 30
ADD 4 40
ADDUP 5 50
VAL 3
VALTREE 3
VALTREE 1
7 4 5
0
1
2
2
2
1
2
ADD 6 76
ADDUP 1 49
ADD 4 48
ADDUP 2 59
VALTREE 1
VALTREE 5
VAL 5
VALTREE 2
VAL 2
Sample Output
80
130
250
291
0
0
107
59
Explanation
In the first sample case, at the end of app the operations, the values at each of the nodes is as follows
1: 60
2: 20
3: 80
4: 40
5: 50
Also, the sum of the values of all the nodes in the subtree rooted at each of the nodes is as follows
1: 250
2: 20
3: 130
4: 40
5: 50| Report Duplicate | Flag | PURGE
Directi Software Developer