A park has n junctions labelled 0 .. n-1 joined by n - 1 two-way trails edges
(edges[i] = [u, v]). Every junction can be reached from every other, and there are no loops, so the
network is a tree. A hike walks along trails without visiting any junction twice.
Return the number of trails on the longest possible hike.
Examples
Input: n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[4,5]]
Output: 4
Explanation: 0 - 1 - 3 - 4 - 5 (or 2 - 1 - 3 - 4 - 5) uses 4 trails.
0 2
\ /
1
|
3 - 4 - 5
Input: n = 1, edges = []
Output: 0
Input: n = 2, edges = [[0,1]]
Output: 1
Constraints
1 <= n <= 2 * 10**4,len(edges) == n - 1, the edges form a tree.- Target
O(n)time.
Goals
- Build an adjacency list for a tree given as an edge list
- Find the farthest node from a start with BFS
- Use two searches to find the longest path in the tree