找到不属于任何树木直径的边缘 [英] Find the edge which is not a part of any possible diameter of a tree
问题描述
我很好奇是否有一种快速的方法来查找是否存在一个边缘，该边缘不是n元树的任何可能直径的一部分。例如，在下面的树中，A-B边缘将不是任何直径的一部分。
I'm curious if there is a quick way to find if an edge exists which is not a part of any possible diameter of a n-ary tree. For example in the following tree, A-B edge will not be a part of any diameter.
我尝试列出所有可能的方法直径，但这会花费很多时间，而且我敢肯定有一种更快的方法。
I tried by listing down all the possible diameters, but that takes a lot of time and I'm certain that there is a faster way.
推荐答案
让我们从一个一个更简单的问题：我们将如何找到树的任何直径？一种方法是选择一个节点，然后在该节点处植树。然后可以通过以下两种方式之一找到图形的直径：
Let's begin with a simpler question: how would we find any diameter of the tree? One way to do this would be to pick some node and to root the tree at that node. A diameter of the graph then could be found in one of two ways:
- 直径可以完全包含在这些子树之一中。 / li>
- 可以通过获取两个子树的根，计算从每个子树根开始的最长路径，然后通过整个树的根将它们连接在一起来找到直径。
因此，假设我们递归地访问每个子树，并从每个子树中获得从该子树的根部开始的最长路径（我们可以隐式存储该路径） （通过让每个节点存储其高度）和纯粹在该子树内的最长路径的长度（可能通过用该树内最长路径的长度标记每个子树来隐式存储）。获得这些信息后，我们可以找到如下所示的 直径：直径为
So imagine that we recursively visit each subtree and obtain, from each, both the longest path starting at the root of that subtree (we could store this implicitly by having each node store its height) and the length of the longest path purely within that subtree (possibly stored implicitly by tagging each subtree with the length of the longest path within that tree). Once we have this information, we can find some diameter as follows: the diameter is either
- 最长的路径
- 完全在这些子树之一中，或者通过从根开始在子树的根开始连接两个最长路径而形成。
所有这些信息都可以通过O（n）辅助存储在时间O（n）中进行计算，因此，如果我们只需要确定直径是多少，我们就可以很快地完成。
All this information can be computed in time O(n) with O(n) auxiliary storage, and so if we just need to determine what the diameter is, we can do so fairly quickly.
现在，让我们对其进行修改，以实际找到所有可能使用的边缘。我们可以从根节点开始。考虑通过路径（1）和（2）获得的路径的长度。如果路线（1）产生的路径比路线（2）严格更长，我们可以递归地进入包含该长度路径的每个子树，并运行相同的过程来识别可能使用的边缘。如果路线（2）产生的路径比路线（2）严格更长，则我们将从根到其具有最长路径（从子树根开始）的每个子项的边标记为已使用，并且如果存在这样的子树然后我们将标记为使用第二长路径的每个子树标记为正在使用。然后，我们递归地进入这些子树，始终沿包含许多可能最长路径之一的子树向下走。
Now, let's modify this to actually find all the edges that might get used. We can do this by starting at the root node. Consider the lengths of the paths obtained via routes (1) and (2). If route (1) produces a strictly longer path than route (2), we can recursively descend into each subtree containing a path of that length and run the same process to identify the edges that could potentially be used. If route (2) produces a strictly longer path than route (2), we'd then mark the edge from the root to each of its children who have the longest path starting at a subtree root as being used, and if there's exactly one such subtree we'd then mark each subtree tied for the second-longest path as being used. We'd then recursively descend into those subtrees, always taking paths down subtrees containing one of the many possible longest paths.
第二个传播步骤花费时间O（n），因为每个节点仅被访问一次，完成的工作与子节点的数量成正比。总的来说，这是一个使用O（n）空间的O（n）时间算法。
This second propagation step takes time O(n) because each node is visited exactly once and the work done is proportional to the number of children. Overall, this is an O(n)-time algorithm that uses O(n) space.
这篇关于找到不属于任何树木直径的边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
