树中最近的节点
Nearest node in a tree
最近我在树上遇到了这个问题，我在 O(n*q) 中找到了解决方案。我在想是否有更好的方法来处理这个复杂度较低的问题。
问题如下：
给定一棵 'n' 节点的未加权树（ n>=1 并且 n 可以达到 105 ），它的节点可以是特殊的或非特殊的。节点 1 始终是特殊的，最初是非特殊的。现在，有两个操作：
1.we可以通过"U Node_Number""U Node_Number"
或
2.At 任何时候，我们可以询问用户 "Q Node_Number" 哪个应该 return最接近 "Node_Number".
的树中的特殊节点
这些操作最多也可以达到105.
我的解决方案：
我想到了创建邻接表。对于操作 1，我可以通过布尔标志记录特殊或非特殊。但是对于操作 2 ，我的解决方案包括每当 "Q Node_Number" 被要求以 "Node_Number" 作为根开始我的 BFS 时执行 BFS。
但是复杂度是二次方的。这是解决这个问题的最佳方法吗？
这是一个通过 sqrt 分解的 O(n^1.5 + n^0.5 q) 时间算法。我们需要一个恒定时间距离的预言机（这基本上是最不常见的祖先）。这个想法是，每 n^0.5 次一个节点变得特殊，从所有特殊节点执行广度优先搜索，这为树中的每个节点产生最近的当前特殊节点。在每个查询中，取最近的 (i) 上次广度优先搜索时特殊的节点 (ii) 最多 n^0.5 个新的特殊节点。
正如我在评论中提到的，我希望通过 top trees.
有一个非常复杂的 O((n + q) log n) 时间算法
最近我在树上遇到了这个问题，我在 O(n*q) 中找到了解决方案。我在想是否有更好的方法来处理这个复杂度较低的问题。
问题如下：
给定一棵 'n' 节点的未加权树（ n>=1 并且 n 可以达到 105 ），它的节点可以是特殊的或非特殊的。节点 1 始终是特殊的，最初是非特殊的。现在，有两个操作：
1.we可以通过"U Node_Number""U Node_Number"
或
2.At 任何时候，我们可以询问用户 "Q Node_Number" 哪个应该 return最接近 "Node_Number".
的树中的特殊节点这些操作最多也可以达到105.
我的解决方案：
我想到了创建邻接表。对于操作 1，我可以通过布尔标志记录特殊或非特殊。但是对于操作 2 ，我的解决方案包括每当 "Q Node_Number" 被要求以 "Node_Number" 作为根开始我的 BFS 时执行 BFS。
但是复杂度是二次方的。这是解决这个问题的最佳方法吗？
这是一个通过 sqrt 分解的 O(n^1.5 + n^0.5 q) 时间算法。我们需要一个恒定时间距离的预言机（这基本上是最不常见的祖先）。这个想法是，每 n^0.5 次一个节点变得特殊，从所有特殊节点执行广度优先搜索，这为树中的每个节点产生最近的当前特殊节点。在每个查询中，取最近的 (i) 上次广度优先搜索时特殊的节点 (ii) 最多 n^0.5 个新的特殊节点。
正如我在评论中提到的，我希望通过 top trees.
有一个非常复杂的 O((n + q) log n) 时间算法