P12563 [UTS 2024] Remove Node

给定一棵包含 $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$ 为根的子树通过操作合并为单个节点的最小总成本。

第一行包含一个整数 $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$)。

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

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