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

ENTRADA	SAÍDA
5 2 5 1 4 6 1 7 1 1 3 5 3 6	1 0 1 0 0
ENTRADA	SAÍDA
5 9 7 8 6 5 1 1 2 1 3 1 4 1	4 3 2 1 0

Enviar solução: Codeforces