FUN WITH TREES

All submissions for this problem are available.
Chef has started learning trees. After finishing the theoretical concepts , he started solving exercise questions. He successfully solved all the question but got stuck in this one. Given a rooted tree with N nodes numbered from 1 – N with node 1 as root. You are also given two types of operation.
Type 1 : x y val ( Add the value val to all the nodes that are coming in the from node x to node y inclusively )
Type 2 : x ( Find the sum of values of all the children of node x inclusively)
There are total U operations of Type 1 and Q operations of Type 2. For each operation of Type 2, Chef has to calculate the required answer modulo 1000000007. Please help the chef, to successfully complete the exercise by completely solving this problem.
Initially all the nodes have value zero.
Input
First line of input contain three space separated numbers N U Q.
Then next N1 lines contain two space separated integers x y, meaning there is an edge between node x and node y describing the nodes position in the tree.
Next U lines follow the Type 1 operation. Then next Q lines follow the Type 2 operation.
Output
For each operation of Type 2 output the required answer modulo 1000000007
Constraints
1 ≤ N ≤ 100000 1 ≤ U ≤ 100000 1 ≤ Q ≤ 100000 10^9 ≤ val ≤ 10^9 1 ≤ x,y ≤ N
Example
Input: 3 1 3 1 2 1 3 2 3 3 1 2 3 Output: 9 3 3
Explanation Tree structure is 1 is root and 2 & 3 are children of 1. Initial value at each node is v(1)=0,v(2)=0,v(3)=0. Type 1 operation Path b/w node 2 and node 3 is 213 Adding 3 to each of the node in the path. Now,v(1)=3,v(2)=3,v(3)=3 Type 2 operation x=1 then answer will v(1)+v(2)+v(3) (whole sub tree at node x) i.e 3+3+3=9. Similarly, for x=2, asnwer is 3 and x=3 answer is 3.
Author:  deebhatia 
Tags  deebhatia 
Date Added:  19032015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions