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