Deeply Rooted Tree in Vitaly Garden

All submissions for this problem are available.
An old Gardner came to Little Vitaly's Garden and gave her a rooted tree T and an integer d.
Each node of the rooted tree has a weight A_{i}. Each A_{i} belongs to a set of positive integers.
Assume the tree is rooted an node indexed 1.
The old Gardner defines a path as a sequence of nodes < v_{0}, v_{1}, v_{2}, ..., v_{k} > where k ≥ 0.
The weight of a path is the sum of node weights for all nodes in the path. Old gardner loves progressions and various kind of manipulations of mathematical series.
A path is said to be a geometric path if Depth(v_{i+1}) = Depth(v_{i}) + d^{i} .
A function f(u) is defined as sum of weight of all geometric paths starting from u.
He asks little Vitaly to find sum of function f(u) modulo 10^{9} + 7 for all nodes u where u belongs to [1, N].
The Depth of a node is the number of edges from the node to the tree's root node.
Note : Vi+1 has to be in subtree of node Vi.
Input
 The first line of Input contains N and d denoting number of nodes and the ratio respectively.
 Next line contains N single space separated integers denoting the weights of the respective nodes.
 Next N  1 lines contain two integers u and v denoting the edge between node u and node v.
Output
 A single integer denoting sum of weight of all geometric paths.
Constraints
 1 ≤ N ≤ 10^{5}
 2 ≤ d ≤ 10
 1 ≤ A_{i} ≤ 10^{5}
 1 ≤ u , v ≤ N
Example
Input: 6 2 2 4 8 16 32 64 1 2 2 3 3 4 4 5 5 6 Output: 466
Explanation
Example case 1.
The paths in the sample test case are 
<1>, <2>, <3>, <4>, <5>, <6>, <1,2> ,<2,3>, <3,4>, <4,5>, <5,6>, <1,2,4>, <2,3,5> and <3,4,6>.
The sum of weights = 2 + 4 + 8 + 16 + 32 + 64 + (2 + 4) + (4 + 8) + (8 + 16) + (16 + 32) + (32 + 64)
+ (2 + 4 + 6) + (4 + 8 + 32) + (8 +16 + 64) = 466.
Author:  dragonslayerx 
Tags  dragonslayerx 
Date Added:  23032016 
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