#4389. ZYB and Trees

题目描述

最初有一棵带点权的树。
给出下列操作：
1 x y z 在x为根的树里，y到根路径链加z
2 x y z x~y链上点权都修改为z
3 x y 在x为根的树里，对y子树的点权求和
4 x y x~y链上取点权max
5 x y x~y链上求点权和
6 x y 连接 x~y
7 x y 断开 x~y

保证操作1~5上x和y在同一棵树上。
保证6和7操作合法（即操作前后都是森林）。

输入格式

第一行一个数N。
第二行N个数表示最开始N个数的权值。
接下来N-1行，每行一个数xi。第i行表示xi和i+1有一条边。
接下来一个数M表示操作数。
接下来M行每行3个或4个数，形式如上。
N,M<=200000
1<=x,y<=N
1<=z<=500000
一共有4组数据。不卡常数。

输出格式

对于每一个3~5操作输出答案。
保证结果不超过long long。

样例

样例输入

5  

1 1 1 1 1  

1 1 1 1  

7  

1 1 2 1  

2 3 4 1  

3 3 4  

4 1 5  

5 1 3  

7 1 2  

6 1 2

样例输出

1  

1  

2

数据范围与提示