Directi Interview QuestionSoftware Developers
- 0of 0 votes
You 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.
The root of the tree is labeled 1. Hence P 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).
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.
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.
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.
5 5 3
ADD 1 10
ADD 2 20
ADD 3 30
ADD 4 40
ADDUP 5 50
7 4 5
ADD 6 76
ADDUP 1 49
ADD 4 48
ADDUP 2 59
In the first sample case, at the end of app the operations, the values at each of the nodes is as follows
Also, the sum of the values of all the nodes in the subtree rooted at each of the nodes is as follows