我听说的想法是使用二进制提升方法找到这两个节点的最低公共祖先(LCA)。要了解更多信息:
https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Lowest%20Common%20Ancestor%20(LCA)
但我不知道在那个算法中我能把重量信息存储在哪里。有什么想法吗?是吗?

最佳答案

为生命周期评价构建一棵树,如下所示。在加权输入树中,找到最重的边,将其删除,然后递归地构造两个(输出)树,每个树对应输入的其余部分。使这些输出树成为新创建根的子级。(基本情况是将单个顶点转换为单个顶点。)
假设我们有一个未开叉的加权树:

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

我们为生命周期评价准备的生根树是:
        5
       / \
      /   \
     /     \
    2       4
   / \     / \
  1   E   D   3
 / \         / \
A   B       C   F

关于algorithm - 如何在树中两个节点之间的路径中找到最重边的权重?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/34423119/

10-08 22:22
查看更多