Description

给定一棵包含 $n$ 个顶点的有根树，每个顶点 $x$ 被赋予一个权值 $a_x$。树的根节点为 $1$ 号节点。

你可以执行以下操作：将两个相邻节点 $x$ 和 $y$ 合并为一个新节点 $z$，$z$ 的权值为这两个节点权值的最小值。该操作会将原本与 $x$ 或 $y$ 相连的边改为与 $z$ 相连。操作的成本为 $|a_x - a_y|$，多次操作的总成本为各次操作成本之和。

你需要处理两种查询：

1. $1\ x\ y$：将节点 $x$ 的权值更新为 $y$；
2. $2\ x$：询问将以 $x$ 为根的子树通过操作合并为单个节点的最小总成本。

Input Format

第一行包含一个整数 $n$ $(1 \le n \le 200\,000)$，表示节点数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^9)$，表示各节点的初始权值。

第三行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$ ($1 \leq p_i \leq n$)，其中 $p_i$ 表示节点 $i$ 的父节点。

第四行包含一个整数 $q$ $(1 \le q \le 200\,000)$，表示查询总数。

接下来 $q$ 行，每行一个查询：

• $1\ x\ y$ ($1 \leq x \leq n$, $1\leq y \leq 10^9$)；
• 或 $2\ x$ ($1\leq x \leq n$)。

Output Format

对于每个类型为 $2$ 的查询，按输入顺序输出一行，表示对应查询的结果。

7
4 7 9 7 4 1 2
1 1 3 2 3 2
1
2 1

11

7
6 6 5 1 6 6 4
1 1 2 3 3 3
3
2 1
1 1 1
2 1

7
11

Hint

• （$4$ 分）：$n \le 1000$，$q=1$；
• （$13$ 分）：$q=1$；
• （$15$ 分）：树为链状且仅包含第二类查询；
• （$24$ 分）：仅包含第二类查询；
• （$12$ 分）：$p_i=1$（所有非根节点的父节点均为根节点）；
• （$32$ 分）：无额外限制。

翻译由 DeepSeek V3 完成