flareon

Flareon

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

!problema/flareon?cute_flareon.png!
 

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.

Fişierul de ieşire $flareon.out$ va conţine elementele şirului $Dmg$, fiecare pe câte un rând.
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$

 
* $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.
h2. Exemplu

11
11 |

!problema/flareon?cute_flareon.jpg!
 

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