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:
https://gist.github.com/samyravitoria/58ca5992380be0f86618ebbb87b4fe12