P6523[DFS序基础]链修改,链查询 | ||
|
问题描述
一棵$n$个节点的有根树,节点编号$1\sim n$,其中$1$是根节点,每个节点上有权值,$m$次操作:
- 1 a b c:将a,b链上的每个节点权值增加c
- 2 a b:查询a,b链上的权值之和
输入格式
第一行两个整数$n,m$。
第二行$n$个整数,表示每个节点的初始权值。
第三行$n-1$个整数,表示$2\sim n$节点的父亲编号。
接下来$m$行,每行一个形如“1 a b c”或者“2 a b”的操作。
输出格式
每次查询输出一行答案。
样例输入 1
5 5
1 2 3 4 5
1 1 3 3
1 1 3 10
2 2 5
1 5 4 20
2 1 4
2 2 5
样例输出 1
31
68
71
样例输入 2
10 10
6 9 10 9 7 9 6 10 8 4
1 1 3 4 5 6 4 8 7
1 6 4 3
2 1 10
1 2 5 9
1 7 6 3
1 4 2 1
2 10 2
1 5 5 9
2 3 5
2 8 4
2 6 6
样例输出 2
60
124
70
32
15
提示
$1\leq n,m,\texttt{初始权值},c\leq 10^6$