6

给定输入一棵树，我们需要回答该类型的查询，

a)给定上述树的一个节点，该节点是距该节点最远的节点。

b)从树中删除一组特定的边。

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

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

所以我上面的解决方案大致是查询的数量O(K*N)在哪里，节点的数量是多少。KN

4

1 回答 1

1

由于您的树是一棵通用树，即它没有平衡甚至有根的概念，因此一次性查询可以做的最好的事情是O(n). 但是，我认为您可以花时间设置树O(n)，然后让每个后续查询花费恒定时间。

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

鉴于评论[和毫无根据的反对票]，似乎解决方案需要更多解释。首先，给定节点的最远节点通常不是唯一的。例如，想象一条正好有三个节点的路径。中间节点有两个最远的节点。其中任何一个都是解决方案。基于此，想法是在树中找到一个节点，该节点位于树中距离最远的两个节点之间的路径中间（这些节点之间的距离是奇数，可以选择任一侧的节点使得距离仅相差 1）：如果最远的节点相距l个节点，则中间节点到它们的路径长度为l/2，或者路径为l/2到 1 和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。

我想，树的预处理可以更优雅地完成，也可能使用少量通道，但我确信上述方法确实有效。

于 2013-11-10T13:02:02.027 回答