for this problem ↵
https://www.codechef.com/DI16R027/problems/TREEUPYou will get 2 points for solving this problem.↵
↵
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[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↵
↵
i write this code↵
https://ideone.com/H0fZZR↵
↵
but this gives me WA plz help me that where i was wrong plz ...............↵
thanx in advance
↵
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[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↵
↵
i write this code↵
https://ideone.com/H0fZZR↵
↵
but this gives me WA plz help me that where i was wrong plz ...............↵
thanx in advance
