c++ - 节点与树中另一个节点的距离最大

Question

给定一个输入树，我们需要回答该类型的查询，
a)给出了上述树的一个节点，该节点是距离该节点最长的节点。
b)从树中删除一组特定的边。

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

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

因此，我上面的解决方案大致是O(K*N)，其中K是查询数，而N是节点数。

Answer 1

由于您的树是一棵普通的树，也就是说，它没有平衡甚至没 Root过的概念，因此对于一次性查询，最好的方法是O(n)。但是，我认为您可以一次花费O(n)时间来设置树，然后让随后的每个查询花费固定的时间。

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

考虑到评论(和毫无根据的批评)，解决方案似乎需要更多的解释。首先，给定节点最远的节点通常不是唯一的。想象一下一个路径，它恰好具有三个节点。中间节点有两个最远的节点。解决方案之一。基于此，我们的想法是在树中找到一个节点，该节点位于树中两个相距最远的节点之间的路径的中间(这些节点之间的距离为奇数，可以选择任一侧的节点这样距离相差仅1):如果相距最远的节点相距l个节点，则中间节点的路径长度均为l/2到它们两个，或者路径长度为l/2到一个且l/2 + 1到另一个。

使用此中间节点将树分成两半，随机分为左右两半，这样就可以确定每个给定节点的相距最远的节点(如果每个节点都知道它在左半部分还是右半部分中):最长的路径将穿过中间节点进入另一半，然后再从那里到达最远离中间节点的节点。让我们将左侧部分ll中最长路径的长度称为右侧部分lr中最长路径的长度。在不失一般性的前提下，将lr
当您要声明与节点n距离最远的节点时，需要考虑以下三种情况:

节点n是中间节点。在这种情况下，最远的节点显然是nl。

节点n在树的右侧。您可以构造的最长路径先到达中间然后再到达nl，即距离最远的节点显然也是nl，也是

节点n在树的左侧。同样，您可以构造的最长路径会到达中间，但会从中间到nr。

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

查找所有叶节点并将它们放入队列，用1标记它们，并给它们指定0的距离。这可以在O(n)时间[和空格]中完成。

从队列中读取(但不要多余)，并找到所有相邻的节点。如果某个节点的标签小于其相邻节点的数量，请增加标签。如果标签现在与相邻节点的数量匹配，则将该节点添加到队列中，并使其距离队列中第一个节点的距离大一个。

如果队列中只有一个节点，则此节点为中间节点，此步骤终止。

否则，请提取前端节点并继续处理队列(即步骤2)。

作为最后一遍，找到具有最大距离标签的相邻节点，并将悬在该节点上的树视为左树。在使用BFS将节点标记为左节点时，请跟踪队列中的最后一个节点以查找nl。将所有其他子树视为正确的树，并用BFS标记它们，作为正确的节点，也找到nr。

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