Weighted Tree Diameter

Problem

Compute the total weight of the longest path in a weighted tree.

Run one traversal from any node to find a farthest node a, then a second traversal from a to find the farthest distance, which is the diameter. edges is a list of [u, v, weight] triples with non-negative weights. Return the diameter weight.

Hint

In a tree, the farthest node from any start is always one endpoint of some diameter.

Test cases

case 1

in: [4,[[0,1,1],[1,2,2],[2,3,3]]]

expected: 6

case 2

in: [4,[[0,1,5],[0,2,1],[0,3,1]]]

expected: 6

case 3

in: [1,[]]

expected: 0

case 4

in: [5,[[0,1,2],[1,2,4],[1,3,1],[3,4,7]]]

expected: 12

Starter codePython

def tree_diameter_weighted(n, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor