Lv.3bfsdfstree
Tree Diameter
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
n villages are connected by n - 1 two-way roads forming a tree; roads[i] = [a, b, len]. Return the largest distance between
any two villages (0 for a single village).
Examples
| n | roads | result |
|---|---|---|
5 | [[0, 1, 3], [1, 2, 4], [1, 3, 2], [3, 4, 6]] | 12 |
2 | [[0, 1, 7]] | 7 |
1 | [] | 0 |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(n: int, roads: int[][]) → long
Constraints
-
n,roads.length, ; the roads form a tree. The answer can exceed 32 bits.
Expected complexity
- Time
- O(N)
- Space
- O(N)
Examples
| n | roads | Expected |
|---|---|---|
5 | [[0,1,3],[1,2,4],[1,3,2],[3,4,6]] | 12 |
2 | [[0,1,7]] | 7 |
1 | [] | 0 |
Hint
Hint
Search from any village to find the farthest u, then search from u; the largest distance found is the diameter. Use an
iterative traversal (deep trees). Searching from every village is .
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 294 ms | estimated |
| C++ (GCC, gnu++23) | 294 ms | derived |
| Python 3.13 | 1108 ms | derived |
| Java 25 | 1632 ms | derived |
| Kotlin 2.4 (JVM) | 1588 ms | estimated |
| C# 14 (.NET 10) | 1588 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 7 | verdict only |
| performance | 60 | 4 | verdict only |