← 返回题目列表

Codeforces · 1178/G

G. 最棒的顶点

中文机器翻译题面 查看原题

您将获得一棵位于 $$$n$$$ 个顶点上的有根树。顶点编号从 $$$1$$$ 到 $$$n$$$;根是顶点号$$$1$$$。

每个顶点都有两个与之关联的整数:$$$a_i$$$ 和 $$$b_i$$$。我们用 $$$R(v)$$$ 表示 $$$v$$$ 的所有祖先的集合(包括 $$$v$$$ 本身)。顶点$$$v$$$的敬畏度定义为

$$$$$$\左| \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$$$ 子树中的最大 Awesomeness。

输入

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

输出

对于第二类型的每个查询,打印各自子树中具有最大敬畏的单行。

示例

输入 #1

5 6
1 1 2 2
10 -3 -7 -3 -10
10 3 9 3 6
2 1
2 2
1 2 6
2 1
1 2 5
2 1

输出 #1

100
91
169
240

注意

顶点的初始敬畏度为 $$$[100, 91, 57, 64, 57]$$$。顶点$$$1$$$(第一个查询)的子树中最棒的顶点是$$$1$$$,顶点$$$2$$$(第二个查询)的子树中最棒的顶点是$$$2$$$。

第一次更新(第三个查询)后,awesomeness 更改为 $$$[100, 169, 57, 160, 57]$$$,因此整个树中最棒的顶点(第四个查询)现在是 $$$2$$$。

在第二次更新(第五个查询)之后,awesomeness 变为 $$$[100, 234, 57, 240, 152]$$$,因此最棒的顶点(第六个查询)现在是 $$$4$$$。