[JRKSJ R8] 暴风雪
题目背景
那边就是最上层了吗……
那里会有什么呢？
题目描述
给你一棵带点权 $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$ 行，每行一个整数表示答案。
输入输出样例
输入样例 #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输出样例 #1
0
6
14
0
0
6
10输入样例 #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输出样例 #2
12
13
13
18
22
28
36
38
46
48输入样例 #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输出样例 #3
9
14
18
22
23
27
27
35
47
47说明
### 数据规模与约定
**本题采用捆绑测试。**
| $\text{Subtask}$ | $n,m\le$ | 特殊性质 | $\text{Score}$ | 时间限制|
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $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 |
对于所有数据，$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$。注意**不保证 $f_i<i$**。
