我们得到了一个具有n个顶点的树，其中一些顶点充当“热点”。
我们必须回答类型（a，b，c）的多个查询，这意味着我们必须找到距c最近的热点的距离，以使我们不会穿过节点a和b之间的边缘。
我已经尝试过许多数据结构，例如在树上使用最低的共同祖先，并且使用过类似mo's算法的算法，但我也尝试过处理最接近根的查询，但是这些都没有给我每个查询所需的复杂度，在O（1）到O（log（n））之间的任何位置。
是否可以使用更好的算法或一些巧妙的预计算（比O（nlogn）少的时间）来解决此问题？
将所有热点合并到单个节点h（代替树-输入现在是图形）。这个问题可以表示如下：
给定无向图G和节点h（合并热点），我们要回答查询Q（c，e）：
Q（c，e）：给定节点c∈G和边e∈G，返回距离（h ，c）在G \ {e}中。
这是一个动态问题，或更具体地说：边缘递减的单源最短路径距离问题（也称为单源边缘去除的精确距离预言”）。
在[1]中，预处理时间为O（mn ^ 1.5 + n ^ 2.5 * logn），查询时间为O（1）。这是一种全对最短路径算法，而您只需要一个单源算法。
[2]将结果改进为O（σ^ 0.5 * n ^ 1.5）预处理时间和O（1）查询时间。 σ是来源数（在您的情况下：σ= 1-合并的热点）。
[2之后，您可以使用O（n ^ 1.5）内存获得O（n ^ 1.5）预处理时间和O（1）查询时间。