樹中最近的節點

Question

最近我遇到了這個問題，我在O（n * q）中找到了解決方案。我在想，是否有更好的方法來處理這種複雜度較低的問題。

的問題是在這裏，如下所示：

鑑於「n」個節點的加權樹（N> = 1且n可以去10 ），它的節點可以是特殊的或非特殊的。節點1總是特殊的，最初休息時間不特別。現在，有兩個操作：

1.我們可以通過「U Node_Number」

OR

2.At隨時更新由更新操作任何非特殊節點特殊節點，我們可以詢問用戶「Q Node_Number」它應該返回最接近「Node_Number」的樹中的特殊節點。

這些操作也可以高達10 。

我的解決方案：

我想創建鄰接列表。對於操作1，我可以通過布爾標誌保留特殊或非特殊的記錄。但是對於操作2，我的解決方案包括每當「Q Node_Number」以「root_Number」作爲root來開始我的BFS時執行BFS。

但是複雜性是二次的。這是解決這個問題的最佳方式嗎？

Answer 1

這是一個通過sqrt分解的O（n^1.5 + n^0.5 q）時間算法。我們需要一個恆定的距離oracle（這基本上是最不常見的祖先）。這個想法是，每個節點的每個n^0.5倍變得特別，從所有特殊節點執行廣度優先搜索，這對樹中的每個節點產生當前特殊的最近節點。在每個查詢中，取最接近的（i）作爲最後廣度優先搜索的特殊節點（ii）最多n^0.5個新特殊節點。

正如我在評論中提到的那樣，我期望通過top trees有一個非常複雜的O（（n + q）log n）時間算法。