QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 2048 MB

# 7446. spxmcq

统计

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