#5706. 「COCI 2024/2025 #3」Stablo

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #3 T4「Bojanje」

Toni 决定为 HONI（和 COCI）出一道题。由于他不喜欢小孩子，他决定让这道题尽可能难。他想出了一个涉及不断变化的树的复杂问题，纯粹是为了让参赛者尽可能痛苦。

给定一棵带有 $N$ 个节点的无权树，树的根节点为 $1$。每个节点都有一个对应的值 $v[i]$。树的结构通过数组 $p[i]$ 定义，其中对于每个 $1 \leq i \leq N-1$，$p[i]$ 表示节点 $i+1$ 的父节点。

对于树中的节点 $y$，函数 $f(y)$ 定义为：

其中 $d(x, y)$ 表示节点 $x$ 和 $y$ 之间的距离，$S_{y}$ 包含以 $y$ 为祖先的所有节点。

给定 $Q$ 个查询，每个查询包含两个节点 $x$ 和 $y$。对于每个查询，必须在树中模拟以下变换，并计算函数 $f(y)$：

1. 将所有以 $x$ 为父节点的节点重新挂载到 $x$ 的父节点下。
2. 从树中移除 $x$。
3. 将节点 $x$ 插回树中，置于 $y$ 和 $x$ 原所属子树中 $y$ 的后代之间。

如果 $y$ 是 $x$ 的父节点，则树保持不变。保证 $x$ 始终位于 $y$ 的子树中。对于每个查询，必须在按照上述过程对树进行临时修改后计算 $f(y)$ 的值。树的修改不是永久的，即每次查询后，树都会恢复到原始状态。

输入格式

第一行包含两个整数 $N$ 和 $Q$ $(1 \leq N, Q \leq 5 \cdot 10^{5})$，分别表示树中节点的数量和查询的数量。

第二行包含 $N$ 个整数 $v[i]$ $(1 \leq v[i] \leq 10^{6})$，表示每个节点的值。

第三行包含 $N-1$ 个整数 $p[i]$ $(1 \leq p[i] \leq i)$，其中 $p[i]$ 表示节点 $i+1$ 的父节点。

接下来的 $Q$ 行中，每行包含两个整数 $x$ 和 $y$ $(1 \leq x, y \leq N)$，表示涉及上述操作的节点。

输出格式

在接下来的 $Q$ 行中，输出修改后树上函数 $f(y)$ 的值。

样例 1

输入

3 1
1 2 3
1 2
3 1

输出

7

在树上应用该操作后，节点 $3$ 距离节点 $1$ 的距离为 $1$，节点 $2$ 距离节点 $1$ 的距离为 $2$。计算结果为 $3+2 \cdot 2=7$。

样例 2

输入

3 2
4 5 6
1 1
2 1
3 1

输出

11
11

样例 3

输入

5 3
2 5 2 2 2
1 2 3 2
4 3
3 2
5 1

输出

2
8
26

数据范围与提示

详细子任务附加限制及分值如下表所示。