== include(page="template/taskheader" task_id="flareon") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $flareon.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $flareon.out$ ...

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

h2. Restricţii
 
* $... ≤ ... ≤ ...$

h2. Restricţii şi precizări
* $1 ≤ N ≤ 200 000$
* $1 ≤ M ≤ 500 000$
* $1 ≤ Power[i] ≤ 1 000 000 000$
* $1 ≤ Pos[i] ≤ 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.

h2. Exemplu
table(example). |_. flareon.in |_. flareon.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

| 4 3
1 1 3
2 2
3 2
4 10
| 10
9
11
11 |

...

!problema/flareon?cute_flareon.jpg!

== include(page="template/taskfooter" task_id="flareon") ==