Wesley's Anger Contest 1 Problem 7 - Arithmetic Subtrees - Olympiads Online Judge

Wesley's Anger Contest 1 Problem 7 - Arithmetic Subtrees

Points: 30 (partial)

Time limit: 3.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 $N$ ~N~ vertices numbered from $0$ ~0~ to $N-1$ ~N-1~, rooted at vertex $0$ ~0~. 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 $P_i$ ~P_i~ for all vertices $i$ ~i~ $(1 \le i \le N-1)$ ~(1 \le i \le N-1)~. For simplicity, we will assume that $0 \le P_i < i$ ~0 \le P_i < i~ for all $i$ ~i~ $(1 \le i \le N-1)$ ~(1 \le i \le N-1)~.

Let $d(i)$ ~d(i)~ be the depth of vertex $i$ ~i~ and $d(0) = 0$ ~d(0) = 0~. Then $d(i) = d(P_i) + 1$ ~d(i) = d(P_i) + 1~ for all $i$ ~i~ $(1 \le i \le N-1)$ ~(1 \le i \le N-1)~. We define the subtree of vertex $u$ ~u~ to be all vertices $v$ ~v~ where $d(u) \le d(v)$ ~d(u) \le d(v)~ and $u$ ~u~ is on the unique path from vertex $0$ ~0~ to vertex $v$ ~v~. Each vertex has a value, initially equal to $0$ ~0~.

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

Input Format	Description
`UPDATE u a b c`	For all vertices $v$ ~v~ in the subtree of $u$ ~u~ with $a \le d(v) \le b$ ~a \le d(v) \le b~, add $c \times (d(v) - d(u))$ ~c \times (d(v) - d(u))~ to the value of vertex $v$ ~v~
`QUERY u a b`	Output the sum of the values of all vertices $v$ ~v~ in the subtree of $u$ ~u~ with $a \le d(v) \le b$ ~a \le d(v) \le b~

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	$N, Q$ ~N, Q~	Additional Constraints
$1$ ~1~	$5\%$ ~5\%~	$2 \le N \le 1\,000$ ~2 \le N \le 1\,000~ $1 \le Q \le 1\,000$ ~1 \le Q \le 1\,000~	None
$2$ ~2~	$10\%$ ~10\%~	$2 \le N \le 100\,000$ ~2 \le N \le 100\,000~ $1 \le Q \le 100\,000$ ~1 \le Q \le 100\,000~	$P_i = i-1$ ~P_i = i-1~
$3$ ~3~	$10\%$ ~10\%~	$2 \le N \le 100\,000$ ~2 \le N \le 100\,000~ $1 \le Q \le 100\,000$ ~1 \le Q \le 100\,000~	$a = 0$ ~a = 0~ and $b = N-1$ ~b = N-1~ for all operations
$4$ ~4~	$10\%$ ~10\%~	$2 \le N \le 100\,000$ ~2 \le N \le 100\,000~ $1 \le Q \le 100\,000$ ~1 \le Q \le 100\,000~	$u = 0$ ~u = 0~ for all operations
$5$ ~5~	$65\%$ ~65\%~	$2 \le N \le 100\,000$ ~2 \le N \le 100\,000~ $1 \le Q \le 100\,000$ ~1 \le Q \le 100\,000~	None

For all subtasks:

$0 \le P_i < i$ ~0 \le P_i < i~ for all $i$ ~i~ $(1 \le i \le N-1)$ ~(1 \le i \le N-1)~

$0 \le u, a, b \le N-1$ ~0 \le u, a, b \le N-1~ for all operations

$0 \le c < 1000$ ~0 \le c < 1000~ for all operations

Input Specification

The first line contains 2 integers, $N$ ~N~ and $Q$ ~Q~.

The next line contains $N-1$ ~N-1~ integers: $P_1, P_2, \dots, P_{N-1}$ ~P_1, P_2, \dots, P_{N-1}~, the parent of each vertex.

The next $Q$ ~Q~ 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 $0$ ~0~.

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

$\text{[math]}$

After the first UPDATE, the values of the vertices are $[0,397,794,794,0]$ ~[0,397,794,794,0]~.

After the second UPDATE, the values of the vertices are $[0,397,794,794,688]$ ~[0,397,794,794,688]~.

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

$\text{[math]}$

After the first UPDATE, the values of the vertices are $[0,0,0,541,1082]$ ~[0,0,0,541,1082]~.

After the second UPDATE, the values of the vertices are $[0,134,268,943,1082]$ ~[0,134,268,943,1082]~.

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

$\text{[math]}$

After the first UPDATE, the values of the vertices are $[0,0,0,0,544]$ ~[0,0,0,0,544]~.

After the second UPDATE, the values of the vertices are $[0,0,55,55,654]$ ~[0,0,55,55,654]~.

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

$\text{[math]}$

After the first UPDATE, the values of the vertices are $[0,667,1334,1334,0]$ ~[0,667,1334,1334,0]~.

After the second UPDATE, the values of the vertices are $[0,667,2568,2568,1851]$ ~[0,667,2568,2568,1851]~.

Comments

4

wleung_bvg commented on April 1, 2025, 6:44 a.m.

Since the original data were weak, an additional batch of test data worth 10 marks was not added, and all submissions were not rejudged. Instead, we have decided to put our efforts into making WAC7 the best contest it can be. Coming soon!

2

BalintR commented on April 2, 2025, 2:55 a.m.

WAC7! When is WAC7? It is currently WAC Year 6 Day 1529.

3

Plasmatic commented on April 1, 2025, 8:14 a.m.

Which part is the fool though?