Informática Avançado – Semana 68

Vedro Pictor e a árvore

O Vedro Pictor possui uma árvore com $$n$$ vértices. A raiz da árvore é o vértice $$1$$. Em cada vértice, Vedro Pictor escreveu um número inteiro positivo, no vértice $$i$$, ela escreveu $$a_i$$. Além disso, a garota escreveu um número inteiro positivo em todas as arestas da árvore (possivelmente, números inteiros diferentes em arestas diferentes). Vamos definir $$dist(v, u)$$ como a soma dos números inteiros escritos nas bordas do caminho simples de $$v$$ a $$u$$. O vértice $$v$$ controla o vértice $$u (v \neq u)$$ se e somente se $$u$$ estiver na subárvore de $$v$$ e $$dist (v, u) \leq a_u$$. Vedro Pictor quer se estabelecer em algum vértice. Para fazer isso, ela quer saber para cada vértice $$v$$ qual é o número de vértices $$u$$ de tal modo que $$v$$ controla $$u$$.

Entrada

A primeira linha contém um número inteiro $$n$$ $$(1 \leq n \leq 2*10^5)$$. A segunda linha contém $$n$$ números inteiros $$a_1, a_2, …, a_n (1 \leq a_i \leq 10^9)$$ – os números inteiros escritos nos vértices. As próximas $$(n – 1)$$ linhas contêm dois números inteiros cada. O $$i$$-ésimo dessas linhas contém números inteiros $$p_i$$ e $$w_i$$ $$(1 \leq p_i \leq n, 1 \leq w_i \leq 10^9)$$ – o pai do $$(i + 1)$$-ésimo vértice na árvore e o número escrito na aresta entre $$p_i$$ e $$(i + 1)$$. É garantido que o gráfico fornecido seja uma árvore.

Saída

Imprima $$n$$ números inteiros – o $$i$$-ésimo desses números deve ser igual ao número de vértices que o $$i$$-ésimo vértice controla.

Exemplos

Enviar solução: Codeforces