1B. 뇌물 바치기 (Bribery)

문제

인덱스국 종교사 : Day 1

인덱스국이 세워지고 얼마 지나지 않아 국왕 (검열됨)은 국력을 과시하기 위한 종교 건축물 건설을 명령했습니다. 그와 신하들은 가장 신성한 자료구조인 스택을 건설하기로 하였고, 수많은 노예들이 스택 건설에 동원되었습니다. 스택 건설은 매우 힘든 일이기 때문에, 노예들은 상관에게 뇌물을 바치고 노동 작업에서 도주하려고 합니다.

노예들의 수장인 1번 노예는 상관을 갖지 않고, 수장이 아닌 각각의 노예는 오직 한 명의 직속 상관을 가진다고 합니다. 바치는 뇌물은 자연수 x, k, a에 의해 결정됩니다. 이는 x번 노예가 노 동으로부터 도주하기 위해 자신의 1번째 (직속) 상관부터 k번째 상관까지, i번째 상관에게 각각 $ai^2$ 원씩의 뇌물을 바쳐야 한다는 것을 의미합니다. 단, 여기서 k(k ≥ 2)번째 상관은 k − 1번째 상관의 직속 상관을 의미합니다.

노예들이 자꾸 도주하기 시작하자 공사는 지지부진해졌고, 대노한 (검열됨)이 대대적인 단 속을 지시했습니다. 인사관리팀장인 당신은 뇌물 사건을 낱낱이 기록하고, (검열됨)의 명령이 들어올 때마다 노예 한 명을 조사하여 그 노예가 받은 뇌물의 양을 (검열됨)에게 보고해야 합 니다.

구현 세부 사항

다음 함수를 구현하시오.

void init(int P[])

이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
P는 크기 N − 1의 배열으로, P[i]는 i + 2번 노예의 직속 상관의 번호입니다. (0 ≤ i ≤ N − 2)

void doju(int x, int k, int a)

이 함수는 Q1번 그레이더에 의해 호출된다.
이 함수가 호출되었을 때, x번 노예가 k, a로 결정되는 형태의 뇌물을 바치고 도주합니다.
k는 x의 상관의 인원수보다 작거나 같음이 보장됩니다.
노예는 도주 직후에 체포되어 업무에 복귀합니다. 따라서 이 함수로 인해 조직도가 바뀌는 일은 없습니다.

int64 investigate(int x)

이 함수는 그레이더에 의해 Q2번 호출됩니다.
이 함수는 현재 시점에서 x번 노예가 받은 뇌물의 양을 반환해야 합니다.

제한 조건

1 ≤ N ≤ 300,000
1 ≤ P[i] ≤ N, P[i] ≠ i (0 ≤ i ≤ N − 2)
자신을 상관으로 가지는 노예는 존재하지 않습니다.
0 ≤ Q1 + Q2 ≤ 300,000
1 ≤ x ≤ N
1 ≤ k
−300 ≤ a ≤ 300

서브태스크

서브태스크	점수	제한 조건
1	2	`k` ≤ 300
2	5	`Q2` ≤ 150
3	8	추가 제한 조건 없음

예제 입출력

N = 8, Q1 = 3, Q2 = 4, P = [4, 1, 3, 1, 4, 5, 4]

그레이더는 다음과 같이 함수를 호출합니다.

init([4, 1, 3, 1, 4, 5, 4])

doju(2, 1, 10)

doju(8, 3, 5)

doju(7, 2, −20)

investigate(2) = 0

investigate(4) = 15

investigate(1) = −35

investigate(5) = −20

샘플 그레이더

Sample Grader는 다음과 같은 형식으로 입력을 받습니다.

line 1 : N Q1 Q2
line 2 : P[0] P[1] ··· P[N − 2]
line 3 + i (0 ≤ i ≤ Q1 + Q2 − 1) : 1 x k a (doju(x, k, a)) or 2 x (investigate(x))