给定一颗 n 个节点有根树,第 i 节点权值为 ai。
在这个树上支持一种询问:
- 给定节点 u 和参数 x,假如 所有节点点权加 x,在这种情况下,求: 对于所有完全在 u 子树内并包含 u 的连通点集,权值之和最大可能为多少?
输入格式
第一行两个正整数 n 和 m。
第二行 n−1 个正整数 f2,f3,…,fn,依次为 2,3,…,n 的父亲节点编号,其中保证 1≤fi<i。
第三行 n 个整数 a1,a2,…,an,依次为 1,2,…,n 点权。
接下来 m 行,每行一个正整数 u 和一个整数 x,代表一组询问,其中保证 1≤u≤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≤n,m≤106,|ai|,|x|≤108,保证 1≤u≤n。