「GLR-R3」谷雨

  「几枝新叶萧萧竹，数笔横皴淡淡山」 ---   十几天前的那条路，还好，两个人一起。   “很幸运呢”，阿绫悄悄嘬一口才破涕为笑的天依，“上天保佑我们要在一……”   鼓着腮掐着软软的腰，天依却又不觉流露笑意，是很幸运呢，刚好入围……   鳞次栉比的尽头，天空似云下起伏的山，皴擦着淡青墨样的欣喜。   她们的故事还在继续，正如谷物正当在今日生长。 ---   **谷雨** 「我翻过一座高山　前方依然　山路漫漫」

老 V 为发挥不错的大家办了场小 party，为了活跃气氛，同时贯彻安全环保的理念，~~（主要还是因为编不出来了，）~~ 老 V 带来了一个高大上的“电子烟花”，美其名曰，火**树**银花。 物如其名，这是一棵含有 $n$ 个结点的树，结点 $u$ 上有点权 $l_u$，表示该结点上所设烟花样式的**绚丽度**。好奇的大家一共对它进行了 $q$ 次操作，不妨记树上从 $u$ 到 $v$ 的路径上的结点（含 $u,v$）构成集合 $P(u,v)$，则每次操作形如： 0. 给定结点编号 $u,v$ 和新的绚丽度 $k$，意为将所有 $\in P(u,v)$，**或者**存在一个邻接点 $\in P(u,v)$ 的结点 $w$ 的绚丽度 $l_w$ **赋值**为 $k$。 1. 给定 $u,v$，点燃这一串烟花最“耀眼”的子段。具体地，维护一个**序列** $S$，从 $u$ 出发沿着树边走向 $v$，当走到结点 $w$（$w$ 可能为 $u$ 或 $v$） 时： - 将 $l_w$ 加入序列 $S$ 的末尾； - **按标号从小到大**枚举 $w$ 的邻接点 $x$，若 $x\notin P(u,v)$，将 $l_x$ 加入 $S$ 的末尾； - 最后，走向下一个结点。 得到最终的 $S$ 后，系统将自动点燃 $S$ 中绚丽度之和最大的子段，子段可能为空。而你需要求出这一和的最大值，即对于每次 1. 操作，求出 $S$ 的**最大可空子段和**。

第一行一个整数 $T$，表示该测试数据所属的子任务编号。 第二行一个整数 $n$，表示树的结点个数。 第三行 $n$ 个整数，第 $i$ 个整数 $l_i$ 表示结点 $i$ 的初始权值。 第四行 $n-1$ 个整数，**为方便选手处理数据，此处假设 $1$ 号结点为树的根。** 第 $i$ 个整数 $p_i$ 表示结点 $i+1$ 的父亲，即表述一条边 $(p_i,i+1)$。**保证 $p_i<i+1$**。 第五行一个整数 $q$，表示需要处理的操作数量。 接下来 $q$ 行，每行格式为 $0~u~v~k$ 或者 $1~u~v$，分别对应了「题目描述」中的两种操作。

输出有若干行，第 $i$ 行应包含一个整数 $a_i$，表示第 $i$ 次 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

#### 样例 #1 解释  本组样例不属于测试数据，故第一行 $T$ 以 $0$ 代替。 第 $1$ 次操作为询问，依次遍历到的结点为 $\lang 1,5,2,3,4\rang$，对应权值队列 $S=\lang 1,5,2,3,4\rang$，最大子段和为 $15$。 第 $2$ 次操作为修改，将结点 $2,1,4,3$ 的点权修改为 $-2$。 第 $3$ 次操作为询问，依次遍历到的结点为 $\lang 3,2,1,4\rang$，对应权值队列 $S=\lang -2,-2,-2,-2\rang$，注意子段可以为空，所以最大子段和为 $0$。 第 $4$ 次操作为修改，将结点 $4,2$ 的点权修改为 $1$。 第 $5$ 次操作为询问，依次遍历到的结点为 $\lang 3,2,1,4\rang$，对应权值队列 $S=\lang -2,1,-2,1\rang$，最大子段和为 $1$。 ### 数据规模与约定 **本题采用 Subtask 的计分方式。** 设 $V$ 为初始点权以及修改操作中点权的值域。 对于 $100\%$ 的数据，$1\le n,q\le10^5$，$1\le p_i\le i$，$V\subseteq[-10^9,10^9]$，操作参数 $1\le u,v\le n$。 对于不同的子任务，作如下约定： | 子任务编号 | $n,q$ | $V$ | 特殊性质 | 子任务分值 | | :--------: | :-------: | :-------------: | :------: | :--------: | | $1$ | $\le10^3$ | $\subseteq[-10^9,10^9]$ | 无 | $10$ | | $2$ | $\le10^5$ | $\subseteq[-10^9,10^9]$ | **A** | $10$ | | $3$ | $\le10^5$ | $\subseteq[-10^9,10^9]$ | **B** | $10$ | | $4$ | $\le10^5$ | $\subseteq[-10^9,10^9]$ | **C** | $15$ | | $5$ | $\le10^5$ | $\subseteq[-10^9,10^9]$ | **D** | $15$ | | $6$ | $\le10^5$ | $\subseteq[0,10^9]$ | 无 | $10$ | | $7$ | $\le10^5$ | $\subseteq[-10^9,10^9]$ | **E** | $20$ | | $8$ | $\le10^5$ | $\subseteq[-10^9,10^9]$ | 无 | $10$ | - **特殊性质 A**：对于所有 $i\in[1,n)$，满足 $p_i=i$。 - **特殊性质 B**：对于所有操作中的参数 $u,v$，满足 $u=v$。 - **特殊性质 C**：不存在修改操作。 - **特殊性质 D**：有且仅有第 $q$ 次操作是询问操作。 - **特殊性质 E**：对于所有**询问操作**中的参数 $u,v$，满足当结点 $1$ 为树根时，$u=v$ 或 $u$ 是 $v$ 的祖先。 - **注意**：输入数据中的 $T$ 仅指该数据点所属子任务编号，该数据点可能满足其他子任务的约束条件。