트리에서 가장 긴 경로

두 친구가 서로에게 프로그래밍 문제를 번갈아 내고 풀며 실력을 겨루고 있습니다. 한 친구가 낸 문제는 다음과 같습니다.

정점이 $N$개이고 각 정점에 $1, 2, \ldots, N$의 번호가 붙은 트리가 주어집니다. 부모가 $0$인 정점이 이 트리의 루트입니다. 루트가 아닌 각 정점 $i$는 자신의 부모와 정수 가중치 $w_i$인 간선으로 이어져 있습니다. 경로의 가중치는 그 경로에 속한 모든 간선의 가중치의 합이며, 단순 경로는 어떤 정점도 두 번 이상 지나지 않는 경로를 말합니다.

다음 두 종류의 질의를 모두 $Q$개 처리해야 합니다.

1. 유형 $1$ ($i$, $w'$): 정점 $i$와 그 부모를 잇는 간선의 가중치를 $w'$로 바꿉니다.
2. 유형 $2$ ($i$): 정점 $i$를 루트로 하는 부분 트리를 생각합니다. 정점 $i$에서 출발하여 이 부분 트리 안에서만 이어지는 단순 경로들 중 가중치가 최대인 값을 출력합니다. 정점 $i$ 하나로만 이루어진 빈 경로의 가중치는 $0$이므로 답은 항상 $0$ 이상입니다.

첫째 줄에 정수 $N$ ($1 \le N \le 10^5$)이 주어집니다.

둘째 줄에 $N$개의 정수 $x_1, x_2, \ldots, x_N$이 주어집니다. 여기서 $x_i$는 정점 $i$의 부모이며, 정점 $i$가 루트이면 $x_i = 0$입니다.

셋째 줄에 $N$개의 정수 $w_1, w_2, \ldots, w_N$이 주어집니다. 여기서 $w_i$는 정점 $i$와 그 부모를 잇는 간선의 처음 가중치입니다 ($-10^9 \le w_i \le 10^9$). 루트의 $w$ 값은 사용되지 않습니다.

넷째 줄에 정수 $Q$ ($1 \le Q \le 10^5$)가 주어집니다.

다음 $Q$개의 줄에는 각각 하나의 질의가 주어집니다. 각 줄은 질의의 종류를 나타내는 정수 $T$ ($1 \le T \le 2$)로 시작합니다.

• $T = 1$이면 뒤에 두 정수 $i$ ($1 \le i \le N$)와 $w'$ ($-10^9 \le w' \le 10^9$)가 옵니다.
• $T = 2$이면 뒤에 하나의 정수 $i$ ($1 \le i \le N$)가 옵니다.

유형 $2$ 질의마다 그 답을 입력에 나타난 순서대로 한 줄에 하나씩 출력합니다. 가중치가 최대인 경로는 가중치가 $0$인 단일 정점 경로일 수도 있으므로, 모든 답은 $0$ 이상입니다.