#139. 树链剖分

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: larryzhong

题目描述

这是一道模板题。

给定一棵 n 个节点的树,初始时该树的根为 1 号节点,每个节点有一个给定的权值。下面依次进行 m 个操作,操作分为如下五种类型:

  • 换根:将一个指定的节点设置为树的新根。

  • 修改路径权值:给定两个节点,将这两个节点间路径上的所有节点权值(含这两个节点)增加一个给定的值。

  • 修改子树权值:给定一个节点,将以该节点为根的子树内的所有节点权值增加一个给定的值。

  • 询问路径:询问某条路径上节点的权值和。

  • 询问子树:询问某个子树内节点的权值和。

输入格式

第一行一个整数 n ,表示节点的个数。

第二行 n 个整数表示第 i 个节点的初始权值 a_i

第三行 n-1 个整数,表示 i+1 号节点的父节点编号 f_{i+1}\ (1 \leqslant f_{i+1} \leqslant n)

第四行一个整数 m ,表示操作个数。

接下来 m 行,每行第一个整数表示操作类型编号: (1 \leqslant u, v \leqslant n)

  • 若类型为 1 ,则接下来一个整数 u ,表示新根的编号。

  • 若类型为 2 ,则接下来三个整数 u,v,k ,分别表示路径两端的节点编号以及增加的权值。

  • 若类型为 3 ,则接下来两个整数 u,k ,分别表示子树根节点编号以及增加的权值。

  • 若类型为 4 ,则接下来两个整数 u,v ,表示路径两端的节点编号。

  • 若类型为 5 ,则接下来一个整数 u ,表示子树根节点编号。

输出格式

对于每一个类型为 4 5 的操作,输出一行一个整数表示答案。

样例

样例输入

6
1 2 3 4 5 6
1 2 1 4 4
6
4 5 6
2 2 4 1
5 1
1 4
3 1 2
4 2 5

样例输出

15
24
19

数据范围与提示

对于 100\% 的数据, 1\leqslant n,m,k,a_i\leqslant 10^5 。数据有一定梯度。