P7889 "MCOI-06" Eert Tuc Knil

Given a rooted tree with $n$ nodes, the weight of node $i$ is $a_i$. This tree supports the following type of query: - Given a node $u$ and a parameter $x$, **suppose** the weights of all nodes are increased by $x$. **Under this assumption, find:** among all connected sets of nodes that are completely inside the subtree of $u$ and that contain $u$, what is the maximum possible sum of weights?

The first line contains two positive integers $n$ and $m$. The second line contains $n-1$ positive integers $f_2,f_3,\dots,f_n$, which are the parent node indices of nodes $2,3,\dots,n$ respectively, and it is guaranteed that $1\le f_i

Output $m$ lines, each containing one integer, which is the answer to the corresponding query.

#### Constraints **This problem uses bundled testdata.** - Subtask 1 (5 pts): $n,m\le 1000$. - Subtask 2 (10 pts): $n,m\le 10^5$ and $|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): no special restrictions. For all testdata, $1\le n,m\le 10^6$, $|a_i|,|x|\le 10^8$, and it is guaranteed that $1\le u\le n$. Translated by ChatGPT 5