You have a rooted tree with vertices, each assigned a value . The root is node .
You can perform operations where you merge two adjacent nodes and into a single node , with the value of being equal to the minimum value between the two nodes. This operation changes edges connected to or to be connected to . The cost of this operation is . The total cost of multiple operations is the sum of individual operation costs.
For queries, you have two types:
: This updates the value of node to .
: This asks for the minimum cost of operations to reduce the subtree rooted at to just one node.
输入格式
The first line contains a single integer , the number of vertices.
The second line contains integers , representing the assigned values of each node.
The third line contains integers (), representing the parent of each node.
The fourth line contains one integer , representing the total number of queries.
The following lines each contain a query:
Either (, ), or ().
输出格式
On each line of the input, you need to print the result of a query of type , in the same order as the order from the input.
样例
样例输入 1
7
4 7 9 7 4 1 2
1 1 3 2 3 2
1
2 1
样例输出 1
11
样例输入 2
7
6 6 5 1 6 6 4
1 1 2 3 3 3
3
2 1
1 1 1
2 1
样例输出 2
7
11
数据范围与提示
( points) ;
( points) ;
( points) the tree is a chain and there are only queries of the second type;
( points) there are only queries of the second type;
