8613: GRL_5_E : Range Query on a Tree II
[Creator : ]
Description
Write a program which manipulates a weighted rooted tree T with the following operations:
-
add(v,w): add w to all edges from the root to node u
-
getSum(u): report the sum of weights of all edges from the root to node u
The given tree T consists of $n$ nodes and every node has a unique ID from 0 to n−1 respectively where ID of the root is 0. Note that all weights are initialized to zero.
Output
For each getSum query, print the sum in a line.
Constraints
All the inputs are given in integers
$2≤n≤100000$
$c_j<c_{j+1}\ (1≤j≤k−1)$
2≤q≤200000
1≤u,v≤n−1
1≤w≤10000
$2≤n≤100000$
$c_j<c_{j+1}\ (1≤j≤k−1)$
2≤q≤200000
1≤u,v≤n−1
1≤w≤10000
Sample 1 Input
6
2 1 2
2 3 5
0
0
0
1 4
7
1 1
0 3 10
1 2
0 4 20
1 3
0 5 40
1 4
Sample 1 Output
0
0
40
150
Sample 2 Input
4
1 1
1 2
1 3
0
6
0 3 1000
0 2 1000
0 1 1000
1 1
1 2
1 3
Sample 2 Output
3000
5000
6000