ACM-ICPC-OJ训练营

问题 1852 --Influence

1852: Influence

时间限制: 8 Sec 内存限制: 300 MB
提交: 2 解决: 2
[提交][状态][讨论版][命题人:]

题目描述

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⋅dis(x,i)),

dis(x,i) means the shortest distance between x and i in tree

输入描述

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≤10

2≤N≤100000

0≤M≤200000

1≤Pi≤i , for

1≤i<N
operation 1 :

1≤x≤N
operation 2 :

2≤x≤N ,

1≤y≤100
operation 3 :

1≤x≤N ,

1≤y≤100

输出描述

For each operation 1 output one integer denotes the answer.

样例输入

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

样例输出

来源

[提交][状态]