如何在树中两个节点之间的路径中找到最重边的权重？ [英] How to find the weight of heaviest edge in the path between two nodes in a tree?

问题描述

我听说过的想法是使用二进制提升方法找到这2个节点的最低公共祖先（LCA）。要了解更多信息：

The idea I have heard about is finding the Lowest Common ancestor (LCA) of these 2 nodes using the binary lifting method. To know more about it:

https://www.topcoder.com/community/data-science/data-science-教程/范围最小查询和最低公共祖先/＃Lowest％20Common％20Ancestor％20（LCA）

但是我不不知道该算法可以在哪里存储重量信息。有什么想法？

But I don't know where in that algorithm I can store the weight information. Any ideas??

推荐答案

为LCA构造一棵树，如下所示。在加权输入树中，找到最重的边，将其删除，然后递归构造两棵（输出）树，输入的每个其余部分各占一棵。使这些输出树成为新创建的根的子代。 （基本情况是将单个顶点转换为单个顶点。）

Construct a tree for LCA as follows. In the weighted input tree, find the heaviest edge, delete it, and construct two (output) trees recursively, one for each remaining component of the input. Make these output trees the children of a newly created root. (The base case is to turn a single vertex into a single vertex.)

假设我们有一棵无根加权树：

Say we have an unrooted weighted tree:

    1     5     4
 A-----B-----C-----D
       |     |
       |2    |3
       |     |
       E     F

我们为LCA准备的根树是：

The rooted tree that we prepare for LCA is:

        5
       / \
      /   \
     /     \
    2       4
   / \     / \
  1   E   D   3
 / \         / \
A   B       C   F

这篇关于如何在树中两个节点之间的路径中找到最重边的权重？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！