题目描述

给定一颗 $n$ 个节点有根树，第 $i$ 节点权值为 $a_i$。

在这个树上支持一种询问：

• 给定节点 $u$ 和参数 $x$，假如 所有节点点权加 $x$，在这种情况下，求： 对于所有完全在 $u$ 子树内并包含 $u$ 的连通点集，权值之和最大可能为多少？

输入格式

第一行两个正整数 $n$ 和 $m$。

第二行 $n-1$ 个正整数 $f_2,f_3,\dots,f_n$，依次为 $2,3,\dots,n$ 的父亲节点编号，其中保证 $1\le f_i<i$。

第三行 $n$ 个整数 $a_1,a_2,\dots,a_n$，依次为 $1,2,\dots,n$ 点权。

接下来 $m$ 行，每行一个正整数 $u$ 和一个整数 $x$，代表一组询问，其中保证 $1\le u\le n$。

输出格式

输出 $m$ 行，每行一个整数，为对应询问的答案。

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

11
4
34
7
-2
-7

提示

Idea：w33z8kqrqk8zzzx33，Solution：w33z8kqrqk8zzzx33&ccz181078，Code：w33z8kqrqk8zzzx33，Data：w33z8kqrqk8zzzx33

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$|a_i|,|x|\le 10^8$，保证 $1\le u\le n$。