QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 2048 MB
[0]
Statistics

给定一颗 n 个节点有根树,第 i 节点权值为 ai

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

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

输入格式

第一行两个正整数 nm

第二行 n1 个正整数 f2,f3,,fn,依次为 2,3,,n 的父亲节点编号,其中保证 1fi<i

第三行 n 个整数 a1,a2,,an,依次为 1,2,,n 点权。

接下来 m 行,每行一个正整数 u 和一个整数 x,代表一组询问,其中保证 1un

输出格式

输出 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% 的数据,满足 1n,m106|ai|,|x|108,保证 1un