P7889 「MCOI-06」Eert Tuc Knil

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

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

#### 数据规模与约定 **本题采用捆绑测试。** - 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$。