Fişierul intrare/ieşire:palatulvoltaic.in, palatulvoltaic.outSursăAlgoritmiada 2019 Runda Maraton
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test2 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Palatulvoltaic

Tanaka a decis sa viziteze locul de unde vine toata electricitatea din univers, mai exact, Palatul Voltaic. Palatul voltaic il putem modela ca pe un arbore cu N noduri, unde nodurile reprezinta turnuri ale palatului, si muchiile reprezinta coridoare ale palatului. In fiecare camera se joaca cate un sport, pasii meciurilor acelui sport furnizand electricitatea Palatului Voltaic. Se stie ca, pentru sportul din camera i, intr-un meci faci exact vi pasi. Odata aflat intr-o camera, poti juca oricate meciuri ale sportului din camera aceea.
Tanaka are, totodata, un pedometru (adica un dispozitiv care masoara cati pasi faci), care poate numara pana la K pasi. Mai exact, in momentul in care Tanaka face cel de-al K+1-lea pas, el se reseteaza si o ia de la 0 (precum kilometrajul la masina).
In vizita sa Tanaka isi incepe drumul dintr-un nod x, ales de el. Apoi, organizatorii palatului ii vor da un numar d ales uniform aleator intre 0 si N - 1. Apoi, Tanaka viziteaza toate nodurile la distanta cel mult d fata de x, jucand sau nu meciuri in camerele acelea. El va alege meciurile la care participa astfel incat la finalul vizitei sale, numarul de pasi pe care il arata pedometrul sau este maximizat. Tanaka ar vrea sa stie, pentru fiecare valoare posibila a lui x de la 1 la N, care este valoarea medie a numarului maxim de pasi pe care il poate arata pedometrul sau, tinand cont ca d este ales aleator uniform intre 0 si N - 1. Puteti calcula aceste valori?

Date de intrare

Fişierul de intrare palatulvoltaic.in va contine, pe primul rand, numerele N si K.
Urmeaza, pe urmatorul rand, N numere, valorile lui v.
Urmeaza, pe urmatoarele N-1 randuri, cate o pereche a, b, ce reprezinta o muchie de la nodul a la nodul b.

Date de ieşire

În fişierul de ieşire palatulvoltaic.out valorile cerute de Tanaka in ordine, pentru x de la 1 la N. Daca o medie ceruta se poate scrie ca fractia ireductibila P / Q, atunci se cere sa se afiseze P * Q-1 (mod 109 + 7), unde Q-1 este inversul modular al lui Q modulo 109+7.

Restricţii

  • 1 ≤ N ≤ 300.000
  • 1 ≤ vi, K ≤ 1.000.000.000
  • Pentru 10 puncte, N ≤ 20 -- feedback testele 1, 3.
  • Pentru alte 30 de puncte, N ≤ 1.000 -- feedback testele 6, 13, 18.
  • Pentru alte 10 puncte, K este ales uniform aleator intre 1 si 1.000.000.000, si valorile lui v sunt alese uniform aleator independent intre 1 si K -- feedback testele 21, 24.
  • Restul testelor de feedback fac parte din testele cele mai mari

Exemplu

palatulvoltaic.inpalatulvoltaic.out
5 11
1 2 3 4 5
1 2
2 3
3 4
3 5
11
600000015
200000012
800000016
11
5 11
2 4 5 6 3
1 2
2 3
3 4
4 5
200000012
800000016
11
10
400000013
9 912672
9409 912673 97 1 912673 912673 1 912673 912673
8 9
4 9
3 9
7 9
2 9
8 5
6 7
1 6
334243917
709856
667579322
912672
608448
811264
912672
709856
811264
10 941191
941192 941192 9604 9604 1 941192 98 941192 941192 941192
6 2
1 2
7 2
10 1
9 10
10 5
4 9
9 8
3 4
600752957
500847056
600937354
700938315
941191
800752939
400941155
500751996
200846113
300847074
9 223092869
223092870 223092870 223092870 223092870 223092870 223092870 223092870 223092870 1
2 1
1 5
2 7
2 9
7 4
9 8
3 8
5 6
62405564
642749220
62405564
482061915
482061915
901718266
62405564
642749220
223092869
9 223092869
223092870 223092870 223092870 223092870 223092870 223092870 223092870 223092870 1
1 6
7 6
4 6
5 7
7 9
7 8
3 9
2 8
482061915
482061915
642749220
482061915
62405564
62405564
642749220
62405564
223092869
10 798335999
24948000 924 124740 4838400 231000 356400 1 12474 1663200 88704000
5 7
7 4
3 7
5 1
4 6
3 10
10 2
9 6
8 9
195818095
498335720
498323523
497852157
498312897
198299275
798335999
598334270
298169611
389465504
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?