Блог пользователя singh1495

Автор singh1495, история, 8 лет назад, По-английски

for this problem You 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

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

You don't clear vec.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You should say didn't instead of don't

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Even if I really should looks like this mistake doesn't hide the meaning. And I'm not sure if it's really a mistake. Can anybody (yeah, no way anybody will read a post called 'need help' from the green guy) prove it?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        Here is proof:

        If you say don't, that means DO NOT DO IT, which is a command to the guy not to clear the vec in the future.

        If you say didn't, that means you point out what is wrong in the past, which means the guy forgot to clear the vec, thus he should clear the vec in the future.

        Thus Don't and Didn't is exactly opposite.

        Proof done.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +15 Проголосовать: не нравится

          I mean proof from someone who is known not only for stupid comments.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I hope you are just trolling and that's not your real intellectual level, there is nothing wrong with his comment.