背景

译自 COCI 2024/2025 #3 T4。$\texttt{2s,0.5G}$。满分为 $120$。

题目描述

给定 $n$ 个节点的有根树，根节点为 $1$。点 $i$ 的点权为 $v_i$。

定义函数

$$f(y)=\sum_{x\in \operatorname{subtree}(y)} \operatorname{dist}(x,y)\cdot v_x$$

其中，$\operatorname{subtree}(y)$ 表示 $y$ 的子树内所有点构成的集合（包括 $y$），$\operatorname{dist}(x,y)$ 表示 $x,y$ 之间的最短路径上的边数。换言之，$f(y)$ 是 $y$ 子树内所有点的点权乘以到 $y$ 的距离求和。

有 $q$ 次操作，每次操作给定两个节点 $x,y$。在一次操作中：

• 将 $x$ 的所有儿子接到 $x$ 的父亲上；
• 将 $x$ 删掉；
• 令 $y$ 的儿子中，包含 $x$ 的为 $z$。将 $x$ 插入到 $y$ 和 $z$ 之间。
• 求出 $f(y)$。

保证 $x\in \operatorname{subtree}(y)$，且 $x\neq y$。特别地，若 $y$ 是 $x$ 的父亲，则原树的形态保持不变。

需要注意的是，操作之间相互独立。也就是说，每次操作都是在初始形态的树上操作（而不是在上一次操作的基础上操作）。

输入格式

第一行，两个正整数 $n,q$。

第二行，$n$ 个正整数 $v_1,v_2,\cdots,v_n$。

第三行，$(n-1)$ 个正整数 $p_2,\cdots,p_n$，其中 $p_i$ 表示 $i$ 号节点的父亲。

接下来 $q$ 行，每行两个正整数 $x,y$，描述一次操作。

输出格式

输出 $q$ 行，每行一个正整数，表示答案。

3 1
1 2 3
1 2
3 1

7

3 2
4 5 6
1 1
2 1
3 1

11
11

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

2
8
26

提示

样例解释

样例 $1$ 中，操作后，有 $\operatorname{dist}(1,3)=1,\operatorname{dist}(1,2)=2$。所求为 $3+2\cdot 2=7$。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n,q\le 5\times 10^5$；
• $1\le v_i\le 10^6$；
• $1\le p_i\lt i$；
• $1\le x,y\in n$；
• $x\neq y$，$x\in \operatorname{subtree}(y)$。

子任务编号	$n,q\le$	特殊性质	得分
$1$	$10^3$		$21$
$2$	$5\times 10^5$	A	$37$
$3$		B	$22$
$4$			$40$

• 特殊性质 A：树的形态是链。换言之，$p_i=i-1$。
• 特殊性质 B：每个节点最多有 $20$ 个儿子。