RoAlgo Contest #7 | cucuruz

Stifon owns $N$ plots of land cultivated with corn, connected by $N-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 $D$ and select another plot $W$, where $W < D$ and $dist(D, W) \leq P$, and collect corn from the plots along the path from $D$ to $W$. Note that for a plot $D$, there can be multiple plots $W$ that satisfy the given conditions. Therefore, Stifon notes $Fss(D)$ as the total sum of corn from each path $(D, W)$ where $W < D$ and $dist(D, W) \leq P$.

Task

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

Input data

The input contains:

• The first line contains two integers $N$ and $P$.
• The second line contains an array $V$ with $N$ elements representing the amount of corn in each plot.
• The next $N-1$ lines contain two numbers $u_i$ and $v_i$ indicating there is a road between plots $u_i$ and $v_i$.

Output data

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

Constraints and clarifications

• $P \leq N \leq 10^5$.
• $V[i] \leq 10^9$ for $1 \leq i \leq N$.
• $dist(D,W)$ is the minimum number of roads on the path from D to W.

Example 1

stdin

3 2
10 5 9 
2 1
1 3

stdout

58

Explanation

For $D = 2$, we can choose $W = 1$ with $Fss(2) = V[1] + V[2] = 10 + 5 = 15$.
For $D = 3$, we can choose either $W = 1$ or $W = 2$, $Fss(3) = V[1] + V[3] + V[1] + V[2] + V[3] = 43$.
$Fss(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!