Fişierul intrare/ieşire:	flareon.in, flareon.out	Sursă	Lot Seniori Alexandria, 2017, baraj 6
Autor	Adrian Budau	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	1.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Flareon

Oraşul Alexandria a fost luat cu asalt de grupuri de durants, pokemoni furnică! Aceştia şi-au construit N muşuroaie numerotate de la 1 la N, conectate între ele prin N-1 tuneluri bidirecţionale, astfel încât să se poată ajunge dintr-un muşuroi în oricare altul urmând tunelurile. Definim distanţa d(i,j) ca fiind egală cu numărul minim de tuneluri care trebuie traversate pentru a ajunge din muşuroiul i în muşuroiul j.
Candela, liderul echipei Valor, a convocat M flareoni, al i-lea dintre aceştia fiind staţionat lângă muşuroiul Pos[i] şi având o mişcare Lava Plume de putere Power[i]. Un atac de tip Lava Plume de putere p efectuat la muşuroiul i, adaugă la gradul de distrugere Dmg[j] al muşuroiului j valoarea max(0, p - d(i, j)).
Se cere să se determine, pentru fiecare muşuroi i, gradul de distrugere Dmg[i] al acestuia după atacurile tuturor celor M flareoni.

Date de intrare

Fişierul de intrare flareon.in va conţine, pe primul rând, pe N şi M.
Pe al doilea rând vor apărea N-1 numere. Considerăm că există un tunel între muşuroiul i+1 şi cel cu indicele egal cu cel de-al i-lea număr.
Urmează M rânduri. Pe fiecare rând va apărea o pereche X P ce reprezintă că există un flareon la muşuroiul X cu puterea P.

Date de ieşire

Fişierul de ieşire flareon.out va conţine elementele şirului Dmg, fiecare pe câte un rând.

Restricţii şi precizări

• 1 ≤ N ≤ 200.000
• 1 ≤ M ≤ 500.000
• 1 ≤ P ≤ 1.000.000.000
• 1 ≤ X ≤ N
• Pentru 20% din teste, N ≤ 1.000 şi M ≤ 2.000
• Pentru 70% din teste, N ≤ 30.000 şi M ≤ 30.000
• Lângă un muşuroi se pot afla mai mulţi flareoni.

Exemplu

Cum se trimit solutii?