Longest Paths in a Tree

Two friends take turns setting and solving programming problems to test each other. One of them poses the following problem.

You are given a tree with $N$ vertices labelled $1, 2, \ldots, N$. The vertex whose parent is $0$ is the root of the tree. Every non-root vertex $i$ is connected to its parent by an edge with an integer weight $w_i$. The weight of a path is the sum of the weights of all edges on it, and a simple path is one that never visits any vertex more than once.

Process $Q$ queries of the following two types.

1. Type $1$ ($i$, $w'$): change the weight of the edge between vertex $i$ and its parent to $w'$.
2. Type $2$ ($i$): consider the subtree rooted at vertex $i$. Among all simple paths that start at vertex $i$ and stay entirely within this subtree, output the maximum possible weight. The empty path consisting of vertex $i$ alone has weight $0$, so the answer is always at least $0$.

The first line contains an integer $N$ ($1 \le N \le 10^5$).

The second line contains $N$ integers $x_1, x_2, \ldots, x_N$, where $x_i$ is the parent of vertex $i$; if vertex $i$ is the root then $x_i = 0$.

The third line contains $N$ integers $w_1, w_2, \ldots, w_N$, where $w_i$ is the initial weight of the edge between vertex $i$ and its parent ($-10^9 \le w_i \le 10^9$). The $w$ value of the root is unused.

The fourth line contains an integer $Q$ ($1 \le Q \le 10^5$).

Each of the next $Q$ lines describes one query and begins with an integer $T$ ($1 \le T \le 2$) giving the query type.

• If $T = 1$, it is followed by two integers $i$ ($1 \le i \le N$) and $w'$ ($-10^9 \le w' \le 10^9$).
• If $T = 2$, it is followed by a single integer $i$ ($1 \le i \le N$).

For every query of type $2$, output its answer on its own line, in the order the queries appear in the input. The maximum-weight path may be the single-vertex path of weight $0$, so every answer is at least $0$.