Background

  “A few new leaves on rustling bamboo, a few strokes of light texture on pale mountains.”

  That road from more than ten days ago was still fine, with two people together.

  “We’re very lucky,” A-Ling quietly took a sip of Tianyi, who had just stopped crying and started smiling, “May heaven bless us to be in a ……”

  Puffing her cheeks and pinching that soft waist, Tianyi could not help but smile as well. They were very lucky, just in time to make it in……

  At the end of rows upon rows, the sky looked like mountains rising and falling under clouds, rubbed with a light cyan ink-like joy.

  Their story continues, just as the crops are growing today.

  Grain Rain “I climbed over a high mountain, yet ahead there is still a long, long mountain road.”

Problem Description

Old V held a small party for everyone who performed well. To liven up the atmosphere, and also to carry out the idea of safety and environmental protection, (mainly because he couldn’t come up with anything else,) Old V brought a fancy “electronic firework,” calling it “firework tree and silver flowers.”

As its name suggests, this is a tree with $n$ nodes. Node $u$ has weight $l_u$, representing the brilliance of the firework style set at that node. Everyone, out of curiosity, performed a total of $q$ operations on it. Let the nodes on the path from $u$ to $v$ in the tree (including $u,v$) form the set $P(u,v)$. Each operation is one of the following:

0. Given node indices $u,v$ and a new brilliance $k$, set the brilliance $l_w$ to $k$ for every node $w$ such that $w\in P(u,v)$, or $w$ has an adjacent node $\in P(u,v)$.

1. Given $u,v$, light the most “dazzling” subsegment of this string of fireworks. Specifically, maintain a sequence $S$. Starting from $u$, walk along tree edges toward $v$. When you reach a node $w$ ($w$ may be $u$ or $v$):

   • Append $l_w$ to the end of sequence $S$.
   • Enumerate $w$’s adjacent nodes $x$ in increasing order of index. If $x\notin P(u,v)$, append $l_x$ to the end of $S$.
   • Finally, move to the next node.

After obtaining the final $S$, the system will automatically light the subsegment of $S$ with the maximum sum of brilliance. The subsegment may be empty. You need to output this maximum value, i.e., for each operation 1., compute the maximum subarray sum allowing emptiness of $S$.

Input Format

The first line contains an integer $T$, indicating the subtask ID to which this testdata belongs.

The second line contains an integer $n$, the number of nodes in the tree.

The third line contains $n$ integers. The $i$-th integer $l_i$ is the initial weight of node $i$.

The fourth line contains $n-1$ integers. To make it easier for contestants to process the data, assume node $1$ is the root of the tree. The $i$-th integer $p_i$ is the parent of node $i+1$, describing an edge $(p_i,i+1)$. It is guaranteed that $p_i<i+1$.

The fifth line contains an integer $q$, the number of operations to process.

The next $q$ lines each have the format $0~u~v~k$ or $1~u~v$, corresponding to the two operations described in “Description.”

Output Format

Output several lines. The $i$-th line should contain an integer $a_i$, the answer to the $i$-th operation of type 1.

0
5
1 2 3 4 5
1 2 2 1
5
1 1 2
0 2 3 -2
1 3 4
0 4 4 1
1 3 4

15
0
1

Hint

Explanation for Sample #1

This sample is not part of the testdata, so the first line uses $T=0$ instead.

The 1st operation is a query. The visited nodes in order are $\lang 1,5,2,3,4\rang$, and the corresponding weight sequence is $S=\lang 1,5,2,3,4\rang$. The maximum subarray sum is $15$.

The 2nd operation is an update, setting the node weights of nodes $2,1,4,3$ to $-2$.

The 3rd operation is a query. The visited nodes in order are $\lang 3,2,1,4\rang$, and the corresponding weight sequence is $S=\lang -2,-2,-2,-2\rang$. Note that the subsegment may be empty, so the maximum subarray sum is $0$.

The 4th operation is an update, setting the node weights of nodes $4,2$ to $1$.

The 5th operation is a query. The visited nodes in order are $\lang 3,2,1,4\rang$, and the corresponding weight sequence is $S=\lang -2,1,-2,1\rang$. The maximum subarray sum is $1$.

Constraints

This problem uses Subtask-based scoring.

Let $V$ be the value range of the initial node weights and the node weights in update operations.

For $100\%$ of the data, $1\le n,q\le10^5$, $1\le p_i\le i$, $V\subseteq[-10^9,10^9]$, and operation parameters satisfy $1\le u,v\le n$.

For different subtasks, the constraints are as follows:

• Special Property A: For all $i\in[1,n)$, $p_i=i$ holds.
• Special Property B: For all operation parameters $u,v$, $u=v$ holds.
• Special Property C: There are no update operations.
• Special Property D: Only the $q$-th operation is a query operation.
• Special Property E: For all parameters $u,v$ in query operations, when node $1$ is the root, either $u=v$ or $u$ is an ancestor of $v$.
• Note: $T$ in the input only indicates the subtask ID of this data point. This data point may satisfy the constraints of other subtasks as well.

Translated by ChatGPT 5