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.
First line of input contain three space separated numbers N U Q.
Then next N-1 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.
For each operation of Type 2 output the required answer modulo 1000000007
1 ≤ N ≤ 100000 1 ≤ U ≤ 100000 1 ≤ Q ≤ 100000 -10^9 ≤ val ≤ 10^9 1 ≤ x,y ≤ N
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 2-1-3 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.
|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|
Fetching successful submissions