Средне Решена: 1 Процент решений: 100.0%

Tree Diameter

A tree is a connected undirected graph with no cycles.

Чему вы научитесь

  • Находить самую дальнюю вершину обходом
  • Получать диаметр двумя запусками BFS
  • Представлять дерево списками смежности

Условие

A tree is a connected undirected graph with no cycles. Its diameter is the largest number of edges on a path between any two vertices. Return that length; you do not need to return the path. No root is specified.

Implement tree_diameter(vertices, edges).

Input

vertices: The number of vertices.

edges: Undirected connections [u, v].

Output

Return the diameter measured in edges, not vertices.

Ограничения

1 ≤ vertices ≤ 200,000. Exactly vertices − 1 edges, with distinct endpoints in 1…vertices. Inputs always form a tree. A one-vertex tree has diameter 0.

Примеры

Пример 1
Ввод:
vertices = 5
edges = [
    [1, 2],
    [2, 3],
    [3, 4],
    [2, 5]
]

Ожидаемый вывод:
expected = 3
Ввод:
long long vertices = 5;
std::vector<std::vector<long long>> edges = {
    {1, 2},
    {2, 3},
    {3, 4},
    {2, 5}
};

Ожидаемый вывод:
long long expected = 3;
Ввод:
long vertices = 5;
long[][] edges = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 4},
    new long[] {2, 5}
};

Ожидаемый вывод:
long expected = 3;

Пояснение

The path 5–2–3–4 contains three edges. No path in this tree is longer.

Пример 2
Ввод:
vertices = 1
edges = []

Ожидаемый вывод:
expected = 0
Ввод:
long long vertices = 1;
std::vector<std::vector<long long>> edges = {};

Ожидаемый вывод:
long long expected = 0;
Ввод:
long vertices = 1;
long[][] edges = new long[][] {};

Ожидаемый вывод:
long expected = 0;

Пояснение

A single vertex has no edges, so the longest path length is 0.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

В tree самый длинный путь можно найти двумя graph searches, а не перебором всех пар вершин.

Подсказка 2

Начни из любой вершины, найди самую далёкую, затем запусти поиск ещё раз от неё, чтобы измерить максимальную distance.

Подсказка 3

Считай edges, а не vertices, и помни, что дерево из одной вершины имеет diameter zero.

Ожидаемая сложность

время O(vertices), доп. память O(vertices)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

# Участник Язык Время Память Оценка ИИ Решение
1 ННикита Python 825 ms - 5/5 Посмотреть код

Учитесь у других

Решения сообщества

Внимание, спойлер: ниже 1 полное решение Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.