# CFR 740 D. Alyona and a tree ( Monotonicity )

Problem - D - Codeforces

O( N lg N ) / O( N )

int N;
vi A;
vvp G;

void init(){
cin >> N;
A = vi( N );
for( int i = 0; i < N; ++i )
cin >> A[ i ];
G = vvp( N );
for( int i = 1; i < N; ++i ){
int P, W; cin >> P >> W;
G[ P - 1 ].emplace_back( W, i );
}
}

vi ans;

void dfs( int u, int fa, ll d, vector< pair< ll, int > > &chain ){ // dis( u, v ) ≤ a( u ) -> d( u ) - d( v ) ≤ a( u ) -> d( u ) - a( u ) ≤ d( v ) -> ++ans[ v ]
++ans[ u ];
auto it = lower_bound( chain.begin(), chain.end(), make_pair( d - A[ u ], -1 ) );
if( it-- != chain.begin() )
--ans[ it->second ];
chain.emplace_back( d, u );
for( int i = 0; i < G[ u ].size(); ++i ){
int w, v; tie( w, v ) = G[ u ][ i ];
if( v == fa ) continue;
dfs( v, u, d + w, chain );
ans[ u ] += ans[ v ];
}
chain.pop_back();
}

void preprocess(){
ans = vi( N );
vector< pair< ll, int > > _chain; dfs( 0, -1, 0, _chain );
}

void solve(){
for( int i = 0; i < N; ++i )
cout << ans[ i ] - 1 << " \n"[ i + 1 == N ];
}