ADDAP - An easy Problem
Seeing so much companies coming for placement in ISM, BABBU also started coding. After rigorous coding for two months, he got bored in solving problems. Now he wants to become problem setter. In order to set problems he took advice from his friends GOTU and CHHOTU. After having a heavy discussion they came up with a problem which goes like this...
You are given a tree rooted at 1.
And you are given Q number of queries to perform on tree.
For each query you are given u, x and y, where u denotes the node number.
You have to add value x to the node u, x + y to its all children at depth 1 (one), x + 2y to all its children at depth 2, ... x + d*y to all its children at depth d and so on.
Input
First line of input contains N - total number of nodes in tree.
Next N-1 lines contain u and v, i.e. there is and edge between nodes u and v.
Next line contains a single integer Q, indicating total number of queries to perform on tree.
Next Q lines contain u x y.
1 <= N <= 100000
1 <= u <= N
1 <= x, y <= 100000
1 <= Q <= 100000
Output
You have to output final values of each node from 1 to N after performing Q queries.
Since the values may be large print them modulo 1000000007.
Sample
Input: 10 4 9 6 4 7 10 5 3 2 6 1 5 5 10 3 8 7 2 5 7 8 1 1 10 7 7 4 7 1 4 1 2 6 2 Output 14 72 30 108 22 90 50 38 126 30
hide comments
[Rampage] Blue.Mary:
2016-03-18 02:42:00
An (almost same) problem already exists: problem code INS14L.
|
Added by: | ashish kumar |
Date: | 2016-03-17 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |
Resource: | self |