Query on a graph

Time Limit: 6000/3000 MS (Java/Others)

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

Description

You are given a connected simple graph(in which both multiple edges and loops are disallowed) with N nodes and N edges. In this graph each node has a weight, and each edge has the same length of one unit. Define D(u,v) as the distance between node u and node v. Define S(u,k) as the set of nodes x which satisfy D(u,x) ≤ k.
We will ask you to perform some instructions of the following forms.
MODIFY u k d: weight of all nodes in S(u,k) increase by d or decrease by -d.
QUERY u k: ask for the sum of weight of all nodes in S(u,k).
In the beginning, the weight of all nodes are 0.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow. For each test case, in the first line there is an integer N(N ≤ 100000). The i-th line of the next N line describes the i-th edge: two integers u,v denotes an edge between u and v. In the next line, an integer Q(Q ≤ 100000) indicates the number of instructions. Next Q lines contain instructions MODIFY u k d or QUERY u k, where |d|≤ 100 and 0 ≤ k ≤ 2.

Output

For each QUERY instruction, output a integer in a line.

Sample Input

2 6 1 2 2 3 3 4 4 1 4 5 3 6 5 MODIFY 1 1 3 MODIFY 3 1 2 MODIFY 5 2 1 QUERY 3 2 QUERY 4 1 6 1 2 2 3 3 1 1 4 2 5 3 6 5 MODIFY 3 1 5 MODIFY 2 2 2 QUERY 6 1 MODIFY 4 1 -2 QUERY 2 2

Sample Output

21 14 14 28

Hint

jiangzijing2015

Source

2016ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学)

提交代码