Solução Informática Avançado - Semana 68

Solução por Samyra Almeida

Conhecimento prévio necessário:

Sabemos que um nó $u$ controla o nó $v$ se e somente se $v$ estiver na subárvore de $u$ e $dist(u, v) \leq a_v$ . Com isso, note que, para um determinado nó $v$ se nós formos subindo na árvore até acharmos o primeiro nó $a$ tal que $dist(a, v) \leq a_v$ podemos afirmar que todos os nós no caminho de $a$ até $v$ , exceto os nós $a$ e $v$ , controlam $v$ .

Percebendo isso, agora vamos fazer uma dfs a partir do nó $1$ para calcularmos o vetor $dist[]$ , onde $dist[i]$ é igual a distância de $1$ até $i$ . Vale lembrar que na entrada já sabemos quem é o pai de todos os nós, caso contrário, também calcularíamos isso durante a dfs.

Após isso, montamos a sparce table. Agora chame de ans[] o vetor que contém a resposta para os vértices. Com isso, para todo nó $i$ faremos $ans[sparce[i][0]]++$ .

Agora criamos uma outra variável $u$ que inicialmente será igual à $i$ e iremos subindo na tabela enquanto $sparce[u][i]$ existir e $dist[i] - dist[sparce[u][i]] \leq a[i]$ , se isso for verdade faremos $u = sparce[u][i]$ . Ao final, checamos se $space[u][0] != -1$ , ou seja se o pai de u existe, se sim faremos $ans[space[u][0]]--$ , ou seja, indicamos que space[u][0] não cobre $v$ .

E para finalizar o problema, faremos uma outra dfs que se chamará $upd(u, f)$ , sendo $f$ pai de $u$ , que irá atualizar o vetor $ans[]$ . Para dois nós $u$ e $v$ sendo $u$ é pai de $v$ , primeiro chamamos o $upd(v, u)$ e depois atualizamos a resposta de $u$ fazendo $ans[u] += ans[v]$ .

Para maior compreensão, leia o código-solução abaixo:

	#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];
	}

view raw

noic-avancado-s68.cpp

hosted with ❤ by GitHub