RoAlgo Contest #7 | cucuruz

This was the problem page during the contest. Access the current page here.
Time limit: 1s
Memory limit: 64MB
Input:
Output:

“When it feel like living's harder than dying
For me giving up's way harder than trying”

Stifon deține NN parcele de teren cultivate cu porumb, legate prin N1N-1 drumuri bidirecționale, astfel garantându-se că se poate ajunge de la o parcelă la alta pe exact un drum. Stifon se poate poziționa pe o parcelă cu numărul DD și să selecteze altă parcelă WW, W<DW < D cu dist(D,W)Pdist(D, W) \leq P, și să colecteze porumbul de pe parcelele de pe lanțul de la DD la WW. Observăm că pentru o parcelă DD există mai multe parcele WW care respectă cerințele impuse. Prin urmare, Stifon notează Fss(D)Fss(D) ca fiind suma totală a porumbului de pe fiecare lanț (D,W)(D, W) cu W<DW < D și dist(D,W)Pdist(D, W) \leq P.

Cerință

Acum Stifon este foarte indecis din care parcelă să înceapă recoltarea, așa că vă întreabă care este suma totală dacă ar începe din oricare parcelă, mai exact valoarea i=1NFss(i)\displaystyle \sum_{i=1}^{N} Fss(i) mod 109 + 710^9 + 7.

Date de intrare

Pe prima linie se află două numere NN și PP. Pe a doua linie se află un vector VV cu NN elemente reprezentând cât porumb este în fiecare parcelă. Pe urmatoarele N1N-1 linii se află câte 2 numere uiu_i și viv_i însemnând că se află un drum între parcelele uiu_i și viv_i.

Date de ieșire

Pe prima linie se află valoarea ceruta, i=1NFss(i)\displaystyle \sum_{i=1}^{N} Fss(i) mod 109 + 710^9 + 7.

Restricții și precizări

  • PN105P \leq N \leq 10^5.
  • V[i]109  (1iN)V[i] \leq 10^9 \ \ (1 \leq i \leq N).
  • dist(D,W)dist(D,W) = numărul minim de drumuri de pe un lanț de la D la W.
    # Scor Restricții
    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 * 10^4, P \leq 100
    6 10 P=2P = 2
    7 40 Fără restricții suplimentare

Exemplul 1

stdin

3 2
10 5 9 
2 1
1 3

stdout

58

Explicație


Pentru DD = 2 putem alege W=1W = 1 cu Fss(2)=V[1]+V[2]=10+5=15Fss(2) = V[1] + V[2] = 10 + 5 = 15.
Pentru DD = 3 putem alege fie W=1W = 1 sau 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.

Exemplul 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

Explicație

Nuj boss, numără-le singur!

Contest info

Official contest

Start time: 1699171200000

Total duration: 4h0m0s

Status: Ended

Attachments

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