CODEWITHSUNDEEP
algorithmgraph
Themistoklis Haris
Themistoklis Haris

Reputation: 365

How to find the weight of heaviest edge in the path between two nodes in a tree?

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-tutorials/range-minimum-query-and-lowest-common-ancestor/#Lowest%20Common%20Ancestor%20(LCA)

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

Upvotes: 0

Views: 1535

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

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

The rooted tree that we prepare for LCA is:

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

Upvotes: 1

Related Questions