cucuruz

Time limit: 1s Memory limit: 64MB Input: Output:

Stifon owns NN plots of land cultivated with corn, connected by N1N-1 bidirectional roads, ensuring that it is possible to travel from one plot to another on exactly one path. Stifon can position himself on a plot numbered DD and select another plot WW, where W<DW < D and dist(D,W)Pdist(D, W) \leq P, and collect corn from the plots along the path from DD to WW. Note that for a plot DD, there can be multiple plots WW that satisfy the given conditions. Therefore, Stifon notes Fss(D)Fss(D) as the total sum of corn from each path (D,W)(D, W) where W<DW < D and dist(D,W)Pdist(D, W) \leq P.

Task

Help Stifon calculate the total sum if he starts harvesting from any plot, specifically the value i=1NFss(i)\displaystyle \sum_{i=1}^{N} Fss(i) mod 109+710^9 + 7.

Input data

The input contains:

  • The first line contains two integers NN and PP.
  • The second line contains an array VV with NN elements representing the amount of corn in each plot.
  • The next N1N-1 lines contain two numbers uiu_i and viv_i indicating there is a road between plots uiu_i and viv_i.

Output data

The first line contains the required value, i=1NFss(i)\displaystyle \sum_{i=1}^{N} Fss(i) mod 109+710^9 + 7.

Constraints and clarifications

  • PN105P \leq N \leq 10^5.
  • V[i]109V[i] \leq 10^9 for 1iN1 \leq i \leq N.
  • dist(D,W)dist(D,W) is the minimum number of roads on the path from D to W.
# Score Constraints
1 5 N6N \leq 6
2 10 N10N \leq 10
3 5 N100N \leq 100
4 10 N104N \leq 10^4
5 20 N5104,P100N \leq 5 \cdot 10^4, P \leq 100
6 10 P=2P = 2
7 40 No additional constraints

Example 1

stdin

3 2
10 5 9 
2 1
1 3

stdout

58

Explanation

g1.png
For D=2D = 2, we can choose W=1W = 1 with Fss(2)=V[1]+V[2]=10+5=15Fss(2) = V[1] + V[2] = 10 + 5 = 15.
For D=3D = 3, we can choose either W=1W = 1 or W=2W = 2, Fss(3)=V[1]+V[3]+V[1]+V[2]+V[3]=43Fss(3) = V[1] + V[3] + V[1] + V[2] + V[3] = 43.
Fss(1)+Fss(2)+Fss(3)=0+15+43=58Fss(1) + Fss(2) + Fss(3) = 0 + 15 + 43 = 58.

Example 2

stdin

10 3
679062366 599100597 187934521 236893327 61406391 912961000 46426980 729873627 889249584 650085534 
2 1
7 9
5 7
1 3
8 7
4 2
4 9
10 3
6 7

stdout

396699172

Explanation

You count them yourself!

Log in or sign up to be able to send submissions!