问距离树中另一个节点最远的节点

EN

因为您的树是一棵通用树，也就是说，它没有平衡的概念，甚至没有根，所以一次性查询所能做的最好是O(n)。但是，我认为您可以使用O(n)时间设置一次树，然后让下面的每个查询都保持恒定的时间。

其思想是找出树的“中间”，它将树分成大小大致相等的树，称这些部分是任意的，例如左和右。然后，将它们各自部分中的所有节点标记为它们所在的部分，并存储一个离中间最远的左节点和右节点。当您得到一个节点的查询时，只需查看节点的标签，并在另一侧报告存储的节点。

考虑到这一评论和不必要的否决，看来解决方案需要更多的解释。首先，对于给定节点来说，最遥远的节点通常并不是唯一的。例如，设想一条有三个节点的路径。中间节点有两个距离最远的节点。其中任何一个都是解决之道。基于此，我们的思想是在树中找到一个节点，该节点位于树中两个最相距节点之间的路径中间(这些节点之间的距离是奇数的，可以选择两边的一个节点，使得距离仅相差一个)：如果距离最远的节点距离为l个节点，则中间节点有一条长度为l/2到两者的路径，或者1/2到1的路径，另一条路径为l/2+1。

使用这个中间节点将树分成两部分，随机地称为左和右，如果每个节点都知道它是在左边还是右边，那么就可以确定每个节点的最遥远的节点:最长的路径将穿过中间节点进入另一半，从中间到离中间最远的节点。让我们调用左侧第11部分中最长路径的长度和右侧lr部分中最长路径的长度。在不失去通用性的情况下，有lr < ll (只需交换周围的名称)。与中间相距最远的节点称为nl和nr。请注意，如果中间节点中有多个子树，只要其中一个最长路径(或者是唯一的最长路径)位于左侧，则该子树被认为是右侧部分的一部分。

当您想要说明与节点n相距最远的节点时，有三种情况需要考虑。

1. 节点n是中间节点。在这种情况下，最遥远的节点显然是nl。
2. 节点n位于树的右侧。您可以构造的最长路径是中间，然后是nl，也就是说，距离最远的节点显然也是nl。
3. 节点n位于树的左侧。再一次，你能建造的最长的路径是从中间到nr的。

剩下的唯一问题是如何在O(n) time中找到中间节点：

1. 找到所有的叶节点，并将它们放入队列，用1标记它们，并给它们一个0的距离。这可以在O(n)的时间和空间内完成。
2. 从队列中读取第一个节点(但不要额外)，并找到所有相邻节点。如果有一个节点的标签小于其相邻节点的数目，则增加该标签。如果标签现在匹配相邻节点的数量，那么将节点添加到队列中，并给它一个比队列中的第一个节点更大的距离。
3. 如果队列中只有一个节点，则此节点为中间节点，此步骤终止。
4. 否则，提取前端节点并继续处理队列(即步骤2)。

最后一次传递，找到具有最大距离标签的相邻节点，并将该节点上的树挂在左边的树上。在用BFS标记节点为左节点的同时，跟踪队列中的最后一个节点以找到nl。考虑所有其他子树--正确的树--并将它们标记为BFS，作为正确的节点，也可以找到nr。

我想，树的预处理可以做得更优雅，可能也需要很少的传球，但我相信上面的方法确实有效。