noic-avancado-s68.cpp

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second

const int maxn = 2e5+10, maxl = 20;

typedef long long ll;
typedef pair<int, ll> ii;

int n, a[maxn], ans[maxn], sparce[maxn][maxl];
ll dist[maxn];

vector<ii> graph[maxn];

void dfs(int u, int f) // primeira dfs 
{
	for(ii x: graph[u]) // percorro a lista de adjacencia de u
	{
		int v = x.F;

		if(v == f) continue;

		dist[v] = dist[u] + x.S; //  calculo a distancia de 1 até v
		
		dfs(v, u);
	}
}

void build() // monto a sparce table
{
	for(int j = 1 ; j < maxl ; ++j)
	{
		for(int i = 1 ; i <= n ; ++i)
		{
			if(sparce[i][j-1] != -1)
				sparce[i][j] = sparce[sparce[i][j-1]][j-1];
		}
	}
}

void upd(int u, int f) // atualizo o vetor ans
{
	for(ii x: graph[u])
	{
		int v = x.F;

		if(v == f) continue;

		upd(v, u);

		ans[u] += ans[v]; // atualizo o ans[u]
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	memset(sparce, -1, sizeof sparce);

	cin >> n;

	for(int i = 1 ; i <= n ; ++i) cin >> a[i]; // leio o vetor a
	
	for(int i = 2 ; i <= n ; ++i)
	{
		ll w;
		cin >> sparce[i][0] >> w;

		graph[sparce[i][0]].push_back({i, w}); // monto o grafo
		graph[i].push_back({sparce[i][0], w}); // monto o grafo
	}

	dfs(1, -1); // chamo a dfs
	
	build(); // monto a sparce table

	for(int i = 1 ; i <= n ; ++i) // passo por cada nó
	{
		ans[sparce[i][0]]++; // marco o primeiro nó que cobre i

		int u = i;

		for(int j = maxl - 1 ; j >= 0 ; --j) // vou subindo na space table
		{
			if(sparce[u][j] != -1 && dist[i] - dist[sparce[u][j]] <= a[i])
				u = sparce[u][j];
		}

		if(sparce[u][0] != -1) ans[sparce[u][0]]--; // desmarco o primeiro no que não cobre i
	}

	upd(1, -1); // atualizo upd

	for(int i = 1 ; i <= n ; ++i) // imprimo a reposta
		cout << ans[i] << " \n"[i == n];
}