Longest Trail
A park has n camps numbered 0 to n - 1 and exactly n - 1 trails, given in trails as pairs [a, b] with a != b. A trail can be walked both ways, no pair appears twice, and every camp can be reached from every other, so the trails form a tree.
Return the number of trails on the longest route that never visits a camp twice. A park with a single camp has a longest route of 0 trails.
Example 1
n 6
trails [[0,1],[1,2],[1,3],[3,4],[4,5]]
returns 4
The route 2, 1, 3, 4, 5 uses four trails, and no route is longer.
Example 2
n 4
trails [[0,1],[0,2],[0,3]]
returns 2
Every route runs from one leaf through camp 0 to another leaf: two trails.
Constraints
1 <= n <= 50len(trails) == n - 10 <= a, b <= n - 1anda != b- the trails connect all camps and contain no cycle
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Lowest High PassMedium
- Mutual Reach GroupsMedium
- Nodes on a LoopMedium
- Rectangular IslandsMedium
- Rounds of Parallel JobsMedium
- Sealed RoomsMedium
- Smallest Task OrderMedium
- Smallest Team SplitMedium