题目背景

题目描述

给你一棵带点权 $v_i$ 的树，树以 $1$ 为根。初始点权 $v_i$ 均为 $0$。

定义 $\text{dis}(x,y)$ 为树上 $x,y$ 之间的距离，即 $x\to y$ 的简单路径上的边数。

设 $\text{subtree}(x)$ 为树上以 $x$ 为根的子树，定义 $f(x)=\max_{d\ge 0} \sum_{y\in\text{subtree}(x)} v_y[\text{dis}(x,y)=d]$。

现在给出 $m$ 次操作，每次操作中给出 $x,w,y$，先令 $v_x\gets v_x+w$，然后求 $\sum_{i\in \text{subtree}(y)} f(i)$。

输入格式

第一行两个整数 $n,m$。

第二行 $n-1$ 个整数 $f_{2\dots n}$，依次表示结点 $2,3,\dots ,n$ 的父亲。

接下来 $m$ 行，每行三个整数 $x,w,y$。

输出格式

输出共 $m$ 行，每行一个整数表示答案。

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

提示

数据规模与约定

本题采用捆绑测试。

对于所有数据，$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$。