Pourquoi une seconde recherche en profondeur?

Question

Récemment, je suis tombé sur un problème appelé Gravity Tree Je ne pouvais pas le résoudre par moi-même alors j'ai vérifié le editorial. La solution des auteurs consistait à dfs sur les sommets une fois et à former une arborescence de segments où chaque nœud contient la distance du sommet au centre. Puis il mentionne une seconde dfs (je ne sais pas ce que ça fait, j'ai essayé d'imprimer ses structures de données, mais elles n'ont aucun sens, sans savoir ce qu'il essaye de faire). La langue dans laquelle il avait écrit était un peu trop difficile à saisir. Je sais ce que sont les arbres de segments, dfs, propogation paresseux. Mais je ne suis pas capable de comprendre cette solution. Et ne pas connaître la solution me rend très anxieux et je ne suis pas capable de me concentrer sur d'autres choses. Ce serait bien si quelqu'un pouvait donner une explication plus claire. Alors que même les autres qui sont confus sont benifités. merci d'avance :)

Le correcteur est catégorique.

Answer 1

1. Est-ce que vous traversez une ajouter la distance de 1 aux noeuds étant parcourus en profondeur d'abord sur traversal l'arbre du nœud « 1 »

   1a.Now. Ainsi que la distance aux nœuds sous un nœud de 1. Appelons cela Y1. Donc, pour chaque nœud, il y a un Y1 qui contient la somme de la distance de 1 à elle-même et à ses nœuds de sous-arbre. Enregistrez également la somme de la distance au carré et appelons si Y2. Maintenant, nous pouvons également stocker le nombre d'éléments dans le sous-arbre.

Tout le pré-traitement est terminé. Maintenant on demande à la force d'agir sur 1 étant donné que le nœud x est allumé, on peut directement imprimer Y2 [x]. Mais les jambes disent maintenant un autre nœud que 1 dire que vous devez être calculé. Calculez ensuite la distance avec l'ACV. Appelez maintenant cette distance d. Maintenant, nous pouvons modifier Y1 en soustrayant n fois d. et en conséquence modifier Y2 = Y2-n d d + 2Y1 * d ceci est un calcul simple. Par conséquent chaque requête prend le temps de log (n) plus une certaine constante