爲什麼第二次深度先搜索？

Question

最近我遇到一個問題叫Gravity Tree 我無法自己解決，所以我檢查了editorial。作者的解決方案是在頂點一次dfs並形成一個段樹，其中每個節點包含從頂點到中心的距離。然後他提到了第二個dfs（我不知道這是做什麼，我嘗試打印他的數據結構，但他們完全沒有意義，不知道他究竟想要做什麼）。他寫的語言太難以掌握了。我知道什麼是細分樹，dfs，懶散的傳播。但是我無法圍繞這個解決方案。不知道解決方案會讓我感到非常焦慮，我無法專注於其他事情。如果有人能給出更清楚的解釋，那將會很好。所以，即使是其他困惑的人也是有益的。在此先感謝:)

問題的制定者是堅決的。

Answer 1

1. 從節點做一個深度優先遍歷在樹「1」

   1a.Now爲您遍歷從1添加到正在經過的節點的距離。以及從節點1到節點下的節點的距離。我們稱之爲Y1。所以對於每個節點都有一個Y1，它保存從1到它自身及其子樹節點的距離之和。也存儲平方距離的總和，如果Y2，我們來調用。現在另外我們可以存儲子樹內的元素數量。

所有預處理完成。現在要求force對1給定一些節點x打開，我們可以直接打印Y2 [x]。但腿說現在有一個節點比1說你需要計算。然後用LCA計算距離。現在稱這個距離爲d。現在我們可以通過減去n次來修改Y1 d。並相應修改Y2 = Y2-n d d + 2Y1 * d這是簡單的數學。因此，每個查詢需要log（n）時間加上一些常量