题目描述

给定一棵含\(n\)个点的有根树，点的编号为\(1 \sim n\)，其中1号点为根节点，每条边分别有一个正整数边权。
定义\(\text{dist}(u,v)\)为从点\(u\)到点\(v\)的简单路径上所有边的权值之和。每个点设有一个正整数阈值\(a_i, i = 1 \cdots n\)，对于两个点\(v,u(u \ne v)\)，若\(v\)是\(u\)的祖先，且\(\text{dist}(u,v) \leq a_u\)，则称点\(v\)“控制”了点\(u\)。
请你按照编号顺序依次输出每个节点控制了其他多少个点。

输入格式

第一行一个整数\(n\)，表示树上点的个数；
第二行\(n\)个整数\(a_1,a_2 \cdots a_n\)，依次表示每个点的阈值；
下面\(n-1\)行，每行包含两个整数\(f_i, w_i, i = 2 \cdots n\)，依次表示\(i\)号点的父亲为\(f_i\)，它与父亲间边的权值为\(w_i\)。

输出格式

\(n\)个非负整数，依次表示\(1 \sim n\)号点所控制的点的个数。两个数之间用恰好1个空格隔开。

样例

输入

5
2 5 1 4 6
1 7
1 1
3 5
3 6

输出

1 0 1 0 0

数据规模、时空限制

对于30%的数据，\(n \leq 2000\)
对于另外的20%数据，\(i\)号点的父亲必然是\(i-1\)号点，\(i=2 \cdots N\)
对于100%的数据，\(1 \leq n \leq 2 \times {10}^5, \quad 1 \leq p_i \leq n, \quad 1 \leq a_i, w_i \leq {10}^9\)
时间限制1s，空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人：于剑