P10574 [JRKSJ R8] Blizzard.


The layered city can be abstracted as a tree. You are given a tree with node weights $v_i$, rooted at node $1$. Initially, all node weights $v_i$ are $0$. Define $\text{dis}(x,y)$ as the distance between $x$ and $y$ on the tree, i.e., the number of edges on the simple path from $x$ to $y$. Let $\text{subtree}(x)$ be the subtree rooted at $x$. Define $f(x)=\max_{d\ge 0} \sum_{y\in\text{subtree}(x)} v_y[\text{dis}(x,y)=d]$. In other words, $f(x)$ is the maximum, among all depths (levels) in the subtree of $x$, of the sum of node weights on that level. Now there are $m$ operations. In each operation, you are given $x,w,y$. First set $v_x\gets v_x+w$, and then compute $\sum_{i\in \text{subtree}(y)} f(i)$.

The first line contains two integers $n,m$. The second line contains $n-1$ integers $f_{2\dots n}$, which give the parent of nodes $2,3,\dots,n$ in order. The next $m$ lines each contain three integers $x,w,y$.

Output $m$ lines in total. Each line contains one integer, the answer for the corresponding operation.

### Constraints **This problem uses bundled testdata.** | $\text{Subtask}$ | $n,m\le$ | Special Property | $\text{Score}$ | Time Limit | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | | $5$ | 1s | | $2$ | $5000$ | | $15$ | 1s | | $3$ | $3\times10^5$ | $f_i=i-1$ | $10$ | 4.5s | | $4$ | $7\times 10^4$ | | $20$ | 4.5s | | $5$ | $3\times10^5$ | | $50$ | 4.5s | For all testdata, $1\le n,m\le3\times 10^5$, $1\le x,y\le n$, $1\le w \le 10^8$, $1\le f_i\le n$. Translated by ChatGPT 5