Influence

Time Limit: 8000/4000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

Description

You are given a rooted tree with N vertices, numbered from 1 to n, the root is 1.
The weight of edges is 1, the value of vertices is 0 at the beginning.
There are 3 type of operation:
1 x : query the value of vertex x
2 x y : modify the weight of edge to y whose child node is x
3 x y : for every vertex i in the tree, value of it add ($y \cdot dis(x , i)$),
$dis(x , i)$ means the shortest distance between x and i in tree

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with one integer N : the size of the tree.
The next one line contains N-1 integers, ith number Pi denotes there is an edge between i+1 and Pi.
The next line contains one integer M : times of operation.
The next M line, each line contains one operation mentioned above.

Limits
$T \leq 10$
$2 \leq N \leq 100000$
$0 \leq M \leq 200000$
$1 \leq Pi \leq i$ , for $1 \leq i < N$
operation 1 : $1 \leq x \leq N$
operation 2 : $2 \leq x \leq N$ , $1 \leq y \leq 100$
operation 3 : $1 \leq x \leq N$ , $1 \leq y \leq 100$

Output

For each operation 1 output one integer denotes the answer.

Sample Input

2 3 1 1 7 3 1 1 1 2 1 3 2 2 2 3 1 2 1 2 1 3 10 1 1 3 4 4 3 1 1 9 7 2 9 74 3 7 96 1 6 3 7 87 2 5 69 3 10 6 1 5

Sample Output

1 1 5 3 288 1425

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码