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.

Implementare

Programul vostru va conține o funcție:

void solve(int N, int M, int* V, int* Pos, int* Power);

Parametrii $N$, respectiv $M$ reprezintă numărul de mușuroaie, respectiv numărul de flareoni. Parametrul $V$ este un array de lungime $N - 1$, indexat de la 0, elementul de pe poziția $i$ al acestuia reprezentând existența unui tunel între mușuroaiele $i + 2$ și $V[i]$. Parametrii $Pos$ și $Power$ sunt două array-uri de dimensiune $M$, indexate de la 0, cu semnificația că al $i$-lea flareon se află la poziția $Pos[i]$, și are o mișcare Lava Plume de putere $Power[i]$.

Odată ce ați găsit cele $N$ grade de distrugere, trebuie să apelați funcția, implementată de grader:

void answer(long long* Dmg);

Când apelați această funcție trebuie sa transmiteți parametrul $Dmg$, un array de lungime $N$ indexat de la $0$, al $i$-lea element al acestuia reprezentând gradul de distrugere al mușuroiului $i+1$.

Pe lângă funcția pe care o veți implementa, puteți declara variabile locale sau globale și puteți implementa alte funcții ajutătoare. Se recomandă ca variabilele globale și funcțiile să fie declarate cu modificatorul static.

Testare

Pentru a vă testa local soluțiile, vă oferim programul main.cpp și header-ul flareon.h. Programul main.cpp citește din fișierul de intrare flareon.in, apelează funcția solve a concurentului și afișează array-ul $Dmg$ dat ca parametru prin funcția answer în fișierul flareon.out.

Pe prima linie a fișierului flareon.in se află numerele naturale $N$ și $M$. Pe a doua linie se află $N - 1$ numere naturale, reprezentând elementele array-ului $V$. Pe următoarele $M$ linii se află $M$ perechi de întregi, a $i$-a pereche reprezentând numerele $Pos[i]$ și $Power[i]$.
În fișierul de ieșire flareon.out vor fi afișate $N$ numere naturale, al $i$-ulea dintre acestea reprezentând numărul $Dmg[i]$.

Restricții și precizări

• $1 ≤ N ≤ 200 \ 000$
• $1 ≤ M ≤ 500 \ 000$
• 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

flareon.in

4 3
1 1 3
2 2
3 2
4 10

flareon.out

10
9
11
11

Explicație

Funcția solve va primi parametrii: $N = 4$, $M = 3$, $T = \{1, 1, 3\}$, $\text{Pos} = \{2, 3, 4\}$, $\text{Power} = \{2, 2, 10\}$.
Drumurile directe între mușuroaie sunt $(2, 1), (3, 1), (4, 2)$.