如果输入一棵树,我们需要回答类型的查询,
a)
给出了上述树的一个节点,该节点是距离该节点最远的节点。
b)
从树中移除一组特定的边缘。
我已经尝试了很长一段时间了,但我能想到的最好的解决办法是,
对于a
类型的查询,调用dfs
函数将返回O(N)
中最远的节点,但我需要做得更好。对于b
类型的查询,如果存在,只需更新树删除边缘即可。
因此,我上面的解决方案大致是O(K*N)
,其中K
是查询的数量,N
是节点的数量。
发布于 2013-11-10 05:02:02
因为您的树是一棵通用树,也就是说,它没有平衡的概念,甚至没有根,所以一次性查询所能做的最好是O(n)
。但是,我认为您可以使用O(n)
时间设置一次树,然后让下面的每个查询都保持恒定的时间。
其思想是找出树的“中间”,它将树分成大小大致相等的树,称这些部分是任意的,例如左和右。然后,将它们各自部分中的所有节点标记为它们所在的部分,并存储一个离中间最远的左节点和右节点。当您得到一个节点的查询时,只需查看节点的标签,并在另一侧报告存储的节点。
考虑到这一评论和不必要的否决,看来解决方案需要更多的解释。首先,对于给定节点来说,最遥远的节点通常并不是唯一的。例如,设想一条有三个节点的路径。中间节点有两个距离最远的节点。其中任何一个都是解决之道。基于此,我们的思想是在树中找到一个节点,该节点位于树中两个最相距节点之间的路径中间(这些节点之间的距离是奇数的,可以选择两边的一个节点,使得距离仅相差一个):如果距离最远的节点距离为l个节点,则中间节点有一条长度为l/2到两者的路径,或者1/2到1的路径,另一条路径为l/2+1。
使用这个中间节点将树分成两部分,随机地称为左和右,如果每个节点都知道它是在左边还是右边,那么就可以确定每个节点的最遥远的节点:最长的路径将穿过中间节点进入另一半,从中间到离中间最远的节点。让我们调用左侧第11部分中最长路径的长度和右侧lr部分中最长路径的长度。在不失去通用性的情况下,有lr < ll (只需交换周围的名称)。与中间相距最远的节点称为nl和nr。请注意,如果中间节点中有多个子树,只要其中一个最长路径(或者是唯一的最长路径)位于左侧,则该子树被认为是右侧部分的一部分。
当您想要说明与节点n相距最远的节点时,有三种情况需要考虑。
剩下的唯一问题是如何在O(n)
time中找到中间节点:
1
标记它们,并给它们一个0
的距离。这可以在O(n)
的时间和空间内完成。最后一次传递,找到具有最大距离标签的相邻节点,并将该节点上的树挂在左边的树上。在用BFS标记节点为左节点的同时,跟踪队列中的最后一个节点以找到nl。考虑所有其他子树--正确的树--并将它们标记为BFS,作为正确的节点,也可以找到nr。
我想,树的预处理可以做得更优雅,可能也需要很少的传球,但我相信上面的方法确实有效。
https://stackoverflow.com/questions/19888999
复制