{"raw_statement":[{"iden":"background","content":"&emsp;&emsp;「几枝新叶萧萧竹，数笔横皴淡淡山」\n\n---\n\n&emsp;&emsp;十几天前的那条路，还好，两个人一起。\n\n&emsp;&emsp;“很幸运呢”，阿绫悄悄嘬一口才破涕为笑的天依，“上天保佑我们要在一……”\n\n&emsp;&emsp;鼓着腮掐着软软的腰，天依却又不觉流露笑意，是很幸运呢，刚好入围……\n\n&emsp;&emsp;鳞次栉比的尽头，天空似云下起伏的山，皴擦着淡青墨样的欣喜。\n\n&emsp;&emsp;她们的故事还在继续，正如谷物正当在今日生长。\n\n---\n\n&emsp;&emsp;**谷雨**&emsp;「我翻过一座高山　前方依然　山路漫漫」"},{"iden":"statement","content":"老 V 为发挥不错的大家办了场小 party，为了活跃气氛，同时贯彻安全环保的理念，~~（主要还是因为编不出来了，）~~ 老 V 带来了一个高大上的“电子烟花”，美其名曰，火**树**银花。\n\n物如其名，这是一棵含有 $n$ 个结点的树，结点 $u$ 上有点权 $l_u$，表示该结点上所设烟花样式的**绚丽度**。好奇的大家一共对它进行了 $q$ 次操作，不妨记树上从 $u$ 到 $v$ 的路径上的结点（含 $u,v$）构成集合 $P(u,v)$，则每次操作形如：\n\n0. 给定结点编号 $u,v$ 和新的绚丽度 $k$，意为将所有 $\\in P(u,v)$，**或者**存在一个邻接点 $\\in P(u,v)$ 的结点 $w$ 的绚丽度 $l_w$ **赋值**为 $k$。\n\n1. 给定 $u,v$，点燃这一串烟花最“耀眼”的子段。具体地，维护一个**序列** $S$，从 $u$ 出发沿着树边走向 $v$，当走到结点 $w$（$w$ 可能为 $u$ 或 $v$） 时：\n\n    - 将 $l_w$ 加入序列 $S$ 的末尾；\n    - **按标号从小到大**枚举 $w$ 的邻接点 $x$，若 $x\\notin P(u,v)$，将 $l_x$ 加入 $S$ 的末尾；\n    - 最后，走向下一个结点。\n\n得到最终的 $S$ 后，系统将自动点燃 $S$ 中绚丽度之和最大的子段，子段可能为空。而你需要求出这一和的最大值，即对于每次 1. 操作，求出 $S$ 的**最大可空子段和**。"},{"iden":"input","content":"第一行一个整数 $T$，表示该测试数据所属的子任务编号。\n\n第二行一个整数 $n$，表示树的结点个数。\n\n第三行 $n$ 个整数，第 $i$ 个整数 $l_i$ 表示结点 $i$ 的初始权值。\n\n第四行 $n-1$ 个整数，**为方便选手处理数据，此处假设 $1$ 号结点为树的根。** 第 $i$ 个整数 $p_i$ 表示结点 $i+1$ 的父亲，即表述一条边 $(p_i,i+1)$。**保证 $p_i<i+1$**。\n\n第五行一个整数 $q$，表示需要处理的操作数量。\n\n接下来 $q$ 行，每行格式为 $0~u~v~k$ 或者 $1~u~v$，分别对应了「题目描述」中的两种操作。"},{"iden":"output","content":"输出有若干行，第 $i$ 行应包含一个整数 $a_i$，表示第 $i$ 次 1. 操作的答案。"},{"iden":"note","content":"#### 样例 #1 解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/2szx2kdy.png)\n\n本组样例不属于测试数据，故第一行 $T$ 以 $0$ 代替。\n\n第 $1$ 次操作为询问，依次遍历到的结点为 $\\lang 1,5,2,3,4\\rang$，对应权值队列 $S=\\lang 1,5,2,3,4\\rang$，最大子段和为 $15$。\n\n第 $2$ 次操作为修改，将结点 $2,1,4,3$ 的点权修改为 $-2$。\n\n第 $3$ 次操作为询问，依次遍历到的结点为 $\\lang 3,2,1,4\\rang$，对应权值队列 $S=\\lang -2,-2,-2,-2\\rang$，注意子段可以为空，所以最大子段和为 $0$。\n\n第 $4$ 次操作为修改，将结点 $4,2$ 的点权修改为 $1$。\n\n第 $5$ 次操作为询问，依次遍历到的结点为 $\\lang 3,2,1,4\\rang$，对应权值队列 $S=\\lang -2,1,-2,1\\rang$，最大子段和为 $1$。\n\n### 数据规模与约定\n\n**本题采用 Subtask 的计分方式。**\n\n设 $V$ 为初始点权以及修改操作中点权的值域。\n\n对于 $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\n对于不同的子任务，作如下约定：\n\n| 子任务编号 |   $n,q$   |       $V$       | 特殊性质 | 子任务分值 |\n| :--------: | :-------: | :-------------: | :------: | :--------: |\n|    $1$     | $\\le10^3$ | $\\subseteq[-10^9,10^9]$ |    无    |    $10$    |\n|    $2$     | $\\le10^5$ | $\\subseteq[-10^9,10^9]$ |  **A**   |    $10$    |\n|    $3$     | $\\le10^5$ | $\\subseteq[-10^9,10^9]$ |  **B**   |    $10$    |\n|    $4$     | $\\le10^5$ | $\\subseteq[-10^9,10^9]$ |  **C**   |    $15$    |\n|    $5$     | $\\le10^5$ | $\\subseteq[-10^9,10^9]$ |  **D**   |    $15$    |\n|    $6$     | $\\le10^5$ |   $\\subseteq[0,10^9]$   |    无    |    $10$    |\n|    $7$     | $\\le10^5$ | $\\subseteq[-10^9,10^9]$ |  **E**   |    $20$    |\n|    $8$     | $\\le10^5$ | $\\subseteq[-10^9,10^9]$ |    无    |    $10$    |\n\n- **特殊性质 A**：对于所有 $i\\in[1,n)$，满足 $p_i=i$。\n- **特殊性质 B**：对于所有操作中的参数 $u,v$，满足 $u=v$。\n- **特殊性质 C**：不存在修改操作。\n- **特殊性质 D**：有且仅有第 $q$ 次操作是询问操作。\n- **特殊性质 E**：对于所有**询问操作**中的参数 $u,v$，满足当结点 $1$ 为树根时，$u=v$ 或 $u$ 是 $v$ 的祖先。\n- **注意**：输入数据中的 $T$ 仅指该数据点所属子任务编号，该数据点可能满足其他子任务的约束条件。"}],"translated_statement":null,"sample_group":[["0\n5\n1 2 3 4 5\n1 2 2 1\n5\n1 1 2\n0 2 3 -2\n1 3 4\n0 4 4 1\n1 3 4\n","15\n0\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}