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

Vezi solutiile trimise | Statistici

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):

Se da un arbore(cu radacina) cu N noduri, fiecare nod X avand o valoare asociata, val[X].

Exista 2 operatii:
-operatia de update: Noua valoarea a nodului X va fi Y;
-operatia de query: Cat timp radacina nu este stearsa, Zetul alege la intamplare un nod X si va fi nevoit sa bea val[X] shot-uri de tequila, iar mai apoi va sterge subarborele nodului X (inclusiv nodul X). Antonio este curios cate shot-uri de tequila va bea Zetul in medie.

Cerinta

Pentru arborele initial, cat si dupa fiecare operatie de update, Antonio va cere sa aflati valoarea operatiei de query.

Date de intrare

Fisierul de intrare tequila.in va contine pe prima linie doua numere naturale N si M, reprezantand numarul de noduri ale arborelui si numarul de update-uri.
Urmatoarea linie va contine N numere naturale, pentru fiecare nod X (1 ≤ X ≤ N) valoarea asociata initial.
Urmatoarele N linii vor descrie arborele, pentru fiecare nod X (1 ≤ X ≤ N) tatal acestuia.
Urmatoarele M linii vor descrie operatiile de update, si vor fi de forma: X Y (val[X] = Y);

Date de ieşire

În fişierul de ieşire tequila.out va contine M + 1 linii, raspunsul pentru fiecare query.

Restricţii

• Radacina va avea tatal -1.

• 1 ≤ val[X] ≤ 100000 (1 ≤ X ≤ N)
• Rezultatul se va verifica cu o precizie de 10^-5

• Subtask 1 (20 puncte): 1 ≤ N ≤ 20 si nu exista update-uri
• Subtask 2 (10 puncte): 1 ≤ N ≤ 100000, arborele este lant si nu exista update-uri
• Subtask 3 (10 puncte): 1 ≤ N ≤ 100000 si arborele este lant
• Subtask 4 (60 puncte): 1 ≤ N ≤ 100000

Exemplu

Explicaţie

Pentru arborele initial:

Eliminam in ordine nodurile 1: 1/3 * val [1];
Eliminam in ordine nodurile 2 , 1: 1/3 * 1/2 * (val [2] + val [1]);
Eliminam in ordine nodurile 3 , 1: 1/3 * 1/2 * (val [3] + val [1]);
Eliminam in ordine nodurile 2 , 3 , 1: 1/3 * 1/2 * 1 * (val [2] + val [3] + val [1]);
Eliminam in ordine nodurile 3 , 2 , 1: 1/3 * 1/2 * 1 * (val [3] + val [2] + val [1]);

1/3 + 2/6 + 2/6 + 3/6 + 3/6 = 2

Cum se trimit solutii?