Fişierul intrare/ieşire:caterinca.in, caterinca.outSursăAGM 2019, runda finala
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test7 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Caterinca

Nota de traducere: enuntul este tradus din Engleza

Aceasta problema este despre "caterinca", un cuvant romanesc care se traduce, aproximativ, in "smecherie" -- desi o traducere exacta nu este usor de gasit

Tanaka vine in vizita la amicul sau, George Mirihcihc. Casa lui poate fi modelata ca un arbore cu N noduri, unde nodurile sunt camere, si muchiile sunt coridoare. In fiecare camera, se tine cate o petrecere, fiecare petrecere avand cate un indice de caterinca. Cea de a i-a petrecere are indicele de caterinca egal cu ci. Tanaka iubeste numarul prim M. Astfel, cand el ajunge, DJ PyroSava va inmulti indicii de caterinca a tuturor petrecerilor cu un numar aleator prim X, care satisface X < M. Acum, Tanaka este obosit din cauza calatoriei, deci nu poate vizita petrecerile din toate camerele. Astfel, el va alege, in mod aleator, sa viziteze o multime conexa de noduri de marime exact K. Caterinca totala pe care o va trai Tanaka este egala cu produsul indicilor de caterinca (dupa inmultirea lui DJ PyroSava) a tuturor camerelor vizitate. Consideram acum valoarea anticipata a acestei caterinci totale. Sa presupunem ca este p / q. Care este valoarea lui pq-1 mod M (unde q-1 reprezinta inversul modular al lui q fata de M) ?

Date de intrare

Fişierul de intrare caterinca.in va incepe cu un numar T, numarul de teste din fisier.
Fiecare test incepe o linie care contine numerele N, M, K.
A doua linie a unui test va contine N numere intregi, valorile lui ci, in ordine.
Urmatoarele N-1 linii vor contine fiecare cate o pereche i, j, care reprezinta o muchie intre nodul i si nodul j.

Date de ieşire

În fişierul de ieşire caterinca.out se vor afisa cate T randuri, fiecare continand raspunsul pentru cate un test.

Restricţii

  • T ≤ 3
  • 1 ≤ N ≤ 1.000.000
  • 0 ≤ ci ≤ 1.000.000.000
  • 1 ≤ M ≤ 20.000
  • 1 ≤ K ≤ N
  • 1 ≤ NK ≤ 10.000.000

Exemplu

caterinca.incaterinca.out
3
3 23 3
2 3 2
3 1
3 2
4 23 4
2 2 4 3
1 4
2 4
3 2
4 23 4
3 3 3 3
2 4
1 3
2 1
3
15
21
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?