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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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]; | |
| } |