题目描述

给定一颗 $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

提示

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$n,m\le 1000$。
• Subtask 2（10 pts）：$n,m\le 10^5$ 并且 $|a_i|,|x|\le 50$。
• Subtask 3（15 pts）：$n\le 1000$。
• Subtask 4（47 pts）：$n,m\le 10^5$。
• Subtask 5（23 pts）：无特殊限制。

对于所有数据，$1\le n,m\le 10^6$，$|a_i|,|x|\le 10^8$，保证 $1\le u\le n$。