P7897 [Ynoi2006] spxmcq

Given a rooted tree with $n$ nodes, the weight of node $i$ is $a_i$. This tree supports one type of query: - Given a node $u$ and a parameter $x$, **suppose** the weights of all nodes are increased by $x$. **In this situation, find:** among all connected vertex sets that are completely inside the subtree of $u$ and 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. It is guaranteed that $1\le f_i

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

Idea: w33z8kqrqk8zzzx33, Solution: w33z8kqrqk8zzzx33&ccz181078, Code: w33z8kqrqk8zzzx33, Data: w33z8kqrqk8zzzx33 For $100\%$ of the 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