Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2016-08-26 19:28:08.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	tequila.in, tequila.out	Sursă	Junior Challenge 2016
Autor	Alexandru Niculae, Costin Oncescu	Adăugată de	JuniorChallenge2016 •JuniorChallenge2015
Timp execuţie pe test	0.35 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Tequila

Intors acasa de la ONI, Antonio se plimba prin Gradina Publica din Barlad impreuna cu cel mai bun prieten al sau, Zetul.
Antonio ii spune lui Zetul urmatoarea problema, care se va da la JBOI 2016 (informatie sigura, aflata de Antonio):

Antonio si-a imaginat o firma cu N angajati, numerotati de la 1 la N. Fiecare angajat al firmei are cate un sef direct (in afara de seful suprem), iar fiecare angajat are ca sef indirect pe seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata, val_X.

Exista 2 tipuri de operatii:

operatia de update: Noua valoarea asociata angajatului X va fi Y;

operatia de query: Cat timp seful suprem nu este concediat, Zetul alege la intamplare un angajat X si va fi nevoit sa bea val_X shot-uri de tequila, iar apoi il va concedia atat pe X cat si pe toti angajatii care il au ca sef indirect pe X. Antonio este curios cate shot-uri de tequila va bea Zetul in medie. (expected value)

Cerinta

Pentru valorile asociate initial, cat si dupa fiecare operatie de update, Antonio va cere sa aflati raspunsul la operatia de query.

Date de intrare

Fisierul de intrare tequila.in va contine pe prima linie doua numere naturale N si M, reprezantand numarul de angajati ai firmei si numarul de update-uri;
Urmatoarea linie va contine N numere naturale - pentru fiecare angajat X (1 ≤ X ≤ N) valoarea asociata initial;
Urmatoarele N linii vor descrie firma, pentru fiecare angajat X (1 ≤ X ≤ N) seful direct al acestuia;
Urmatoarele M linii vor descrie operatiile de update sub forma: X Y (noua valoare asociata lui X este Y);

Date de ieşire

Fişierul de ieşire tequila.out va contine M + 1 linii, reprezentand raspunsurile pentru fiecare query.

Restricţii si precizari

0 ≤ M ≤ 100000

1 ≤ val_X ≤ 100000 (1 ≤ X ≤ N)

Seful suprem va avea seful direct codificat cu -1.

Fie Y seful direct al angajatului X. Spunem ca un angajat este sef indirect al lui X daca acesta este fie Y, fie un sef indirect al lui Y.

Dupa o operatie de query, Zetul va angaja la loc toti membrii firmei.

Rezultatul afisat se considera corect daca si numai daca $\mid rezultat_c_o_m_i_s_i_e - rezultat_c_o_n_c_u_r_e_n_t \mid \leq 10^-^5$ .

Subtask 1 (30 puncte): 1 ≤ N ≤ 20, M = 0
Subtask 2 (20 puncte): 1 ≤ N * M ≤ 4000000, 1 ≤ M ≤ 4000 si nu vor exista 2 angajati cu acelasi sef direct
Subtask 4 (50 puncte): 1 ≤ N ≤ 100000

Exemplu

tequila.in	tequila.out
3 1 1 1 1 -1 1 1 1 2	2.00000 3.00000

Explicaţie

REMINDER: ASTA NU E ASA v
Exista 5 posibilitati de a concedia angajatii (in ordine):

1) Angajatul 1 cu probabilitatea $\frac{1}{3}$ , iar Zetul va bea $val_1$ shot-uri;
2) Angajatii 2 , 1 cu probabilitatea $$\frac{1}{3} \cdot \frac{1}{2}$, iar Zetul va bea <tex> val_2 + val_1$ shot-uri;
3) Angajatii 3 , 1 cu probabilitatea $$\frac{1}{3} \cdot \frac{1}{2}$, iar Zetul va bea <tex> val_3 + val_1$ shot-uri;
4) Angajatii 2 , 3 , 1 cu probabilitatea $$\frac{1}{3} \cdot \frac{1}{2} \cdot 1$, iar Zetul va bea <tex> val_2 + val_3 + val_1$ shot-uri;
5) Angajatii 3 , 2 , 1 cu probabilitatea $$\frac{1}{3} \cdot \frac{1}{2} \cdot 1$, iar Zetul va bea <tex> val_3 + val_2 + val_1$ shot-uri;

1) Angajatul 1 cu probabilitatea $\frac{1}{3} \cdot val_1$ ;
2) Angajatii 2 , 1 cu probabilitatea $\frac{1}{3} \cdot \frac{1}{2} \cdot (val_2 + val_1)$ ;
3) Angajatii 3 , 1 cu probabilitatea $\frac{1}{3} \cdot \frac{1}{2} \cdot (val_3 + val_1)$ ;
4) Angajatii 2 , 3 , 1 cu probabilitatea $\frac{1}{3} \cdot \frac{1}{2} \cdot 1 \cdot (val_2 + val_3 + val_1)$ ;
5) Angajatii 3 , 2 , 1 cu probabilitatea $\frac{1}{3} \cdot \frac{1}{2} \cdot 1 \cdot (val_3 + val_2 + val_1)$ ;

Pentru valorile asociate initial: $\frac{1}{3} + \frac{2}{6} + \frac{2}{6} + \frac{3}{6} + \frac{3}{6} = 2$ ;
Dupa primul update: $\frac{2}{3} + \frac{3}{6} + \frac{3}{6} + \frac{4}{6} + \frac{4}{6} = 3$ ;