## Wesley's Anger Contest 1 Problem 7 - Arithmetic Subtrees

View as PDF

Points: 30 (partial)
Time limit: 7.0s
Memory limit: 256M

Author:
Problem types

After having lots of fun dealing with arithmetic sequences and squares, you decided to try combining arithmetic sequences and subtrees!

You are given a tree with vertices numbered from to , rooted at vertex . Recall that a tree is a connected graph where there is exactly one path between any two vertices. It can be seen that each vertex has a unique parent for all vertices . For simplicity, we will assume that for all .

Let be the depth of vertex and . Then for all . We define the subtree of vertex to be all vertices where and is on the unique path from vertex to vertex . Each vertex has a value, initially equal to .

You are asked to perform operations on the tree, which come in two forms.

Input Format Description
UPDATE u a b c For all vertices in the subtree of with , add to the value of vertex QUERY u a b Output the sum of the values of all vertices in the subtree of with #### Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

Subtask Points Additional Constraints    None          and for all operations     for all operations    None for all  for all operations for all operations

#### Input Specification

The first line contains 2 integers, and .

The next line contains integers: , the parent of each vertex.

The next lines each contain a valid operation as described above.

#### Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

For each QUERY operation, output the answer on its own line. If there are no vertices that meet the query parameters, then the answer is .

#### Sample Input 1

5 4
0 1 1 3
UPDATE 0 1 2 397
QUERY 0 2 2
UPDATE 3 0 3 688
QUERY 1 1 3

#### Sample Output 1

1588
2673

#### Sample Explanation 1 After the first UPDATE, the values of the vertices are .

After the second UPDATE, the values of the vertices are .

#### Sample Input 2

5 4
0 1 2 3
UPDATE 2 1 4 541
QUERY 0 1 4
UPDATE 0 1 3 134
QUERY 0 4 1

#### Sample Output 2

1623
0

#### Sample Explanation 2 After the first UPDATE, the values of the vertices are .

After the second UPDATE, the values of the vertices are .

#### Sample Input 3

5 4
0 1 1 3
UPDATE 3 0 4 544
QUERY 4 0 4
UPDATE 1 0 4 55
QUERY 0 0 4

#### Sample Output 3

544
764

#### Sample Explanation 3 After the first UPDATE, the values of the vertices are .

After the second UPDATE, the values of the vertices are .

#### Sample Input 4

5 4
0 1 1 3
UPDATE 0 1 2 667
QUERY 0 0 1
UPDATE 0 2 3 617
QUERY 0 2 3

#### Sample Output 4

667
6987

#### Sample Explanation 4 After the first UPDATE, the values of the vertices are .

After the second UPDATE, the values of the vertices are .