Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | caterinca.in, caterinca.out | Sursă | AGM 2019, runda finala |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 3.5 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Caterinca
Nota de traducere: enuntul era original in engleza
Aceasta problema este despre "caterinca", un cuvant Romanesc care se traduce, aproximativ, in "caterinca" sau "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 c_i. 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 c_i, 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 ≤ c_i ≤ 1.000.000.000
- 1 ≤ M ≤ 20.000
- 1 ≤ K ≤ N
- 1 ≤ NK ≤ 10.000.000
Exemplu
table(example). |_. caterinca.in |_. caterinca.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
|
Explicaţie
...
