Background

Problem Description

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)$.

Input Format

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 Format

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

5 7
1 1 1 4
2 1 5
4 2 1
3 4 1
2 5 5
2 4 5
4 4 4
3 2 2

0
6
14
0
0
6
10

6 10
1 1 1 1 2
6 4 1
3 1 1
1 1 1
3 4 1
5 2 1
3 3 1
3 4 1
2 2 1
2 5 1
3 1 1

12
13
13
18
22
28
36
38
46
48

8 10
1 1 2 1 3 3 3
7 3 1
2 4 1
5 2 1
5 2 1
3 1 1
6 2 1
1 4 1
8 4 1
6 4 1
3 2 1

9
14
18
22
23
27
27
35
47
47

Hint

Constraints

This problem uses bundled testdata.

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