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

Question

给定一个树形结构的输入，我们需要回答以下类型的问题:

a) 给定上述树形结构中的一个节点，哪个节点是离该节点最远的节点。

b)从树形结构中移除特定集合的边。

我已经尝试了很长时间，但我能想到的最好解决方案是：

对于类型a的查询，调用dfs函数在O(N)内返回最远的节点，但我需要做得更好。 对于类型b的查询，只需更新树形结构[如果存在，则删除边]。

因此，我以上述解决方案大致为O(K*N)，其中K是查询数量，N是节点数。

- hello

---

K和N的限制是什么？ - Ivaylo Strandjev

两个数都可以达到100000。 - hello

是的，所以我们必须输出在最大距离[在该连通组件内]的节点，如果只剩下一个节点，那个特定的节点将成为答案。 - hello

是的，我们知道这些查询。 - hello

这听起来像是一个并查集问题。尝试任意选择一个根节点，然后找到左/右子树中最深的节点。如果树是平衡的，那么这将为查询提供O(log N)的运行时间。 - kevmo314

Answer 1

由于您的树是一般树，即没有平衡的概念甚至没有根节点，您所能做的最好的一次查询是O(n)。不过，我认为您可以花费O(n)的时间设置树，然后每个随后的查询只需要花费常数时间。

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

根据评论（和不必要的负评），似乎需要更详细的解释。首先，对于给定节点，最远的节点通常不是唯一的。例如，想象一条恰好有三个节点的路径。对于中间节点，有两个最远的节点。其中任一个都是解决方案。基于此，想法是在树中找到一个位于两个最远节点之间路径中点的节点（如果这些节点之间的距离是奇数，则可以选择一侧的节点，使得距离仅相差1）：如果最远的节点相隔l个节点，则中间节点与它们的路径长度为l/2，或者与一个节点的路径长度为l/2，与另一个节点的路径长度为l/2+1。

使用这个中间节点将树分成两半，随机称为左半部分和右半部分，可以确定任何给定节点的最远节点，如果每个节点知道它是在左半部分还是右半部分：最长路径将通过中间节点进入另一半部分，然后从那里到达距离中间最远的节点。我们将左侧部分中最长路径的长度称为ll，将右侧部分中最长路径的长度称为lr。不失一般性，假设lr < ll（只需交换名称即可）。来自中间节点的各自最远的节点称为nl和nr。请注意，如果有多个子树从中间节点引导到被认为是右侧部分的一部分，只要其中一个最长路径（或者如果唯一，则是最长路径）在左侧部分中即可。

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

1. 节点n是中间节点。在这种情况下，最远的节点显然是nl。
2. 节点n位于树的右侧。您可以构造的最长路径经过中间节点，然后到达nl，即最远的节点也是nl。
3. 节点n位于树的左侧。同样，您可以构造的最长路径经过中间节点，但从那里到达nr。

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

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

最后一步，找到具有最大距离标签的相邻节点，并将挂在该节点上的树视为左树。在使用BFS标记节点作为左节点时，保持队列中的最后一个节点以找到nl。将所有其他子树视为右树，并使用BFS标记它们作为右节点，同时也找到nr。

我猜，树的预处理可能可以更优雅地完成，可能只需要进行少量的传递，但我确信上述方法是可行的。

- Dietmar Kühl

---

@IvayloStrandjev：正确。然而，需要注意的是，我并没有建议随意分割！相反，我建议在“中间”分割，这不是很容易找到，但也不是很难，可以在O（n）内完成。不过，我承认，我没有明确说明我所说的中间是什么（指树中位于最远节点之间的位置的节点）。 - Dietmar Kühl

我相信你所说的是“中心”，它位于树的直径的中间。然而，“中心”并不能帮助你找到树中距离任何节点最远的节点。 - Ivaylo Strandjev

@IvayloStrandjev：我可以相信它被称为中心，但它确实有助于找到最远的节点，因为通往最远的节点的任何路径都会经过中心或以中心开始。您将使用一个指示器（在上面的描述中我使用了“左”但这可能是误导性的，“绿色”可能更好）标记从中心到距离中心最远的节点的子树中的节点。如果有多个具有此属性的子树，则只需选择其中之一即可。 - Dietmar Kühl

取消投票。小贴士：要找到树的中心 - 从任何节点运行BFS并找到距离它最远的节点。之后从该节点运行BFS，它将与距离它最远的节点形成直径。中心在直径的中间。顺便说一句，我仍然不确定您的解决方案是否能够在删除边缘时保持结构。 - Ivaylo Strandjev

@IvayloStrandjey：我描述的算法不会改变树的结构。它只是在每个节点上记录信息（访问相邻节点的数量，距离叶子的距离和颜色）。当然，一旦找到颜色，结构就不再需要了。 - Dietmar Kühl