CF1178G The Awesomest Vertex

给定一棵有 $n$ 个节点的有根树，节点编号为 $1$ 到 $n$，根节点为 $1$。 每个节点 $i$ 关联两个整数 $a_i$ 和 $b_i$。我们用 $R(v)$ 表示节点 $v$ 的所有祖先（包括 $v$ 本身）的集合。节点 $v$ 的“awesomeness”（精彩度）定义为 $$ \left| \sum_{w \in R(v)} a_w \right| \cdot \left| \sum_{w \in R(v)} b_w \right| $$ 其中 $|x|$ 表示 $x$ 的绝对值。 你需要处理 $q$ 个操作，操作有以下两种类型： - `1 v x` —— 将 $a_v$ 增加一个正整数 $x$。 - `2 v` —— 查询以节点 $v$ 为根的子树中，精彩度最大的节点的精彩度。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 10^5$），分别表示树的节点数和操作数。 第二行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \leq p_i < i$），其中 $p_i$ 表示节点 $i$ 与节点 $p_i$ 之间有一条边。 第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-5000 \leq a_i \leq 5000$），表示每个节点的初始 $a_i$。 第四行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$-5000 \leq b_i \leq 5000$），表示每个节点的 $b_i$。 接下来的 $q$ 行，每行描述一个操作，格式如下： - `1 v x`（$1 \leq v \leq n$，$1 \leq x \leq 5000$） - `2 v`（$1 \leq v \leq n$）

对于每个类型为 2 的查询，输出一行，表示对应子树中最大的精彩度。

初始时各节点的精彩度为 $[100, 91, 57, 64, 57]$。第一次查询（对节点 $1$ 的子树）最精彩的节点是 $1$，第二次查询（对节点 $2$ 的子树）最精彩的节点是 $2$。 第一次更新（第三个操作）后，精彩度变为 $[100, 169, 57, 160, 57]$，此时整棵树最精彩的节点是 $2$。 第二次更新（第五个操作）后，精彩度变为 $[100, 234, 57, 240, 152]$，此时最精彩的节点是 $4$。 由 ChatGPT 4.1 翻译