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 il are ca sef indirect pe seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata, $val{~X~}$.

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 il are ca sef indirect pe seful suprem. Se mai stie ca fiecare membru al firmei (inclusiv seful suprem) are o valoare asociata, <tex> val_X </tex>.

Exista $2$ tipuri de operatii:

Exista <tex> 2 </tex> tipuri de operatii:

* Update: Noua valoarea asociata angajatului $X$ va fi $Y$;

* Update: Noua valoarea asociata angajatului <tex> X </tex> va fi <tex> Y </tex>;

* 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** (eng. "expected value").

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

h2. Cerinta