Problem Background

Is that the topmost level...

What could be there?

Problem Description

You are given a tree with vertex weights \( v_i \), rooted at 1. Initially, all vertex weights \( v_i \) are 0.

Define \( \text{dis}(x, y) \) as the distance between vertices \( x \) and \( y \) on the tree, which is 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] \).

You are given \( m \) operations. Each operation provides \( x, w, y \). First, update \( v_x \gets v_x + w \), then compute \( \sum_{i \in \text{subtree}(y)} f(i) \).

Input Format

The first line contains two integers \( n \) and \( m \).

The second line contains \( n-1 \) integers \( f_{2 \dots n} \), representing the parent of nodes \( 2, 3, \dots, n \) in sequence.

The next \( m \) lines each contain three integers \( x, w, y \).

Output Format

Output \( m \) lines, each containing a single integer representing the answer.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0
6
14
0
0
6
10

Input Sample #2

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

Output Sample #2

12
13
13
18
22
28
36
38
46
48

Input Sample #3

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

Output Sample #3

9
14
18
22
23
27
27
35
47
47

Notes

Data Size and Constraints

This problem uses subtask testing.

For all data, \( 1 \le n, m \le 3 \times 10^5 \), \( 1 \le x, y \le n \), \( 1 \le w \le 10^8 \), \( 1 \le f_i \le n \). Note that it is not guaranteed that \( f_i < i \).

见题面 Input 部分

见题面 Output 部分