급여 격차

시간 제한10초메모리 제한256 MB

요약

직원의 급여 인상은 해당 직원과 모든 부하의 급여를 같은 금액만큼 올리고 질의는 그 집단의 최고액과 최저액 차이를 구합니다.

난이도: 보통10점 중 5점
유형: 세그먼트 트리, 트리
정답자: 아직 제출이 없습니다

문제

직원이 $N$ 명인 회사가 있다. 직원 한 명을 뺀 나머지 직원 모두에게 직속 상사가 한 명씩 있다. 직속 상사가 없는 직원은 회사의 다른 모든 직원의 간접 상사다. 직원 $Y$ 가 직원 $X$ 의 직속 상사이거나, $X$ 의 직속 상사가 $Y$ 의 부하 직원이면 $X$ 는 $Y$ 의 부하 직원이다.

인사팀은 회사의 급여 격차를 조사하려고 한다. 어떤 직원의 격차는 그 직원과 그 직원의 모든 부하 직원이 받는 급여 중 최댓값에서 최솟값을 뺀 값이다.

직원 한 명이 자신과 자신의 모든 부하 직원의 급여를 같은 금액만큼 올리는 일도 있다. 인상과 격차 질의를 주어진 순서대로 처리하라.

입력

첫 줄에 분석할 회사의 수 $T$ 가 주어진다. $T$ 는 20 이하다.

각 회사는 다음과 같이 주어진다. 첫 줄에 직원 수 $N$ 이 주어진다. 직원에게는 1부터 $N$ 까지 서로 다른 번호가 붙어 있다. 다음 줄에 $N-1$ 개의 정수가 주어지고, 그중 $K$ 번째 정수는 직원 $K+1$ 의 직속 상사 번호다. 다음 줄에 $N$ 개의 정수가 주어지고, 그중 $K$ 번째 정수는 직원 $K$ 의 급여다. 다음 줄에 처리할 사건의 수 $Q$ 가 주어진다. 이어지는 $Q$ 개의 줄에 사건이 한 줄에 하나씩 주어진다. 인상 사건은 문자 R로 시작하고, 직원 번호와 그 직원 및 그 직원의 모든 부하 직원의 급여에 더할 금액이 뒤따른다. 격차 질의는 문자 Q로 시작하고, 격차를 구할 직원 번호가 뒤따른다.

$2 \le N \le 1\,000\,000$
$1 \le Q \le 10\,000$

모든 직원 $K$ 의 직속 상사 번호는 $K$ 보다 작다. 처음 급여는 1 이상 1000 이하이고, 인상 금액도 1 이상 1000 이하다.

출력

격차 질의마다 그 직원의 격차를 한 줄에 하나씩 출력한다.

예제8

예제 1

입력

예상 출력

예제 2

입력

예상 출력

예제 3

입력

1
10
1 2 3 4 5 6 7 8 9
10 20 30 40 50 60 70 80 90 100
10
Q 1
Q 5
Q 10
R 6 1000
Q 1
Q 5
Q 6
R 1 7
Q 1
Q 2

예상 출력

예제 4

입력

1
10
1 1 1 1 1 1 1 1 1
500 1 1000 250 750 500 500 2 999 500
7
Q 1
Q 3
R 3 1000
Q 1
R 2 999
Q 1
Q 2

예상 출력

예제 5

입력

3
3
1 1
5 5 5
4
Q 1
R 2 10
Q 1
Q 2
2
1
1000 1
2
Q 1
Q 2
6
1 2 3 4 5
1 2 3 4 5 6
5
Q 1
R 4 100
Q 3
Q 4
Q 5

예상 출력

예제 6

입력

1
8
1 1 2 2 3 3 4
7 7 7 7 7 7 7 7
8
Q 1
R 1 1000
Q 1
Q 4
R 4 1000
Q 1
Q 4
Q 2

예상 출력

예제 7

입력

1
7
1 1 2 2 3 3
100 200 300 400 500 600 700
8
Q 4
Q 5
Q 6
Q 7
R 4 1000
Q 4
Q 2
Q 1

예상 출력

예제 8

입력

1
5
1 1 2 2
1 1 1000 1 1
9
Q 1
R 5 1000
R 5 1000
R 5 1000
R 5 1000
R 5 1000
Q 1
Q 2
Q 5

예상 출력