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