859. Longest Weighted Road
A delivery company's road network has n depots numbered 0 to n - 1, joined by n - 1 two-way roads, so exactly one route exists between any pair of depots. Each road is given as edges[i] = [a, b, w]: it joins depots a and b and is w kilometres long.
Find the pair of depots whose connecting route is the longest and return that route's total length in kilometres. If there is only one depot, there is no route and the answer is 0. Total lengths can exceed the 32-bit range, so use a 64-bit integer type for the result.
Example 1
- Input:
- n = 5, edges = [[0,1,4],[1,2,3],[1,3,10],[3,4,2]]
- Output:
- 16
- Explanation:
The route 0-1-3-4 is 4 + 10 + 2 = 16 km, longer than 2-1-3-4 (15 km) or 0-1-2 (7 km), so 16 is the longest.
Example 2
- Input:
- n = 4, edges = [[0,1,5],[0,2,6],[0,3,1]]
- Output:
- 11
- Explanation:
All routes pass through depot 0; the longest joins depots 1 and 2: 5 + 6 = 11 km.
Constraints
- 1 ≤ n ≤ 105
edges.length == n - 1, 0 ≤ a, b < n and the roads form a tree- 1 ≤ w ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)