Найдите край, который не является частью какого-либо возможного диаметра дерева

Question

Мне любопытно, есть ли быстрый способ узнать, существует ли ребро, которое не является частью какого-либо возможного диаметра n-арного дерева. Например, в следующем дереве ребро A-B не будет частью какого-либо диаметра.

Я попытался перечислить все возможные диаметры, но это занимает много времени, и я уверен, что есть более быстрый путь.

Answer 1

Давайте начнем с более простого вопроса: как бы мы нашли любой диаметр дерева? Один из способов сделать это - выбрать какой-то узел и получить root права на дерево в этом узле. Диаметр графика затем можно найти одним из двух способов:

1. Диаметр может содержаться только в одном из этих поддеревьев.
2. Чтобы определить диаметр, нужно взять корни двух поддеревьев, вычислить самый длинный путь, начиная с каждого из корней поддерева, а затем соединить их вместе через общий корень дерева.

Итак, представьте, что мы рекурсивно посещаем каждое поддерево и получаем из каждого из них как самый длинный путь, начинающийся в корне этого поддерева (мы могли бы сохранить это неявно, сохраняя высоту каждого узла), так и длину самого длинного пути чисто внутри этого поддерева (возможно, хранится неявно, помечая каждое поддерево длиной самого длинного пути в этом дереве). Получив эту информацию, мы можем найти некоторый диаметр следующим образом: диаметр равен либо

1. самый длинный путь только в одном из этих поддеревьев, или
2. образуется путем соединения двух самых длинных путей, начинающихся у корней поддеревьев через корень.

Вся эта информация может быть вычислена за время O (n) с помощью O (n) вспомогательной памяти, и поэтому, если нам просто нужно определить, каков диаметр, мы можем сделать это довольно быстро.

Теперь давайте изменим это, чтобы найти все ребра, которые могут быть использованы. Мы можем сделать это, начиная с корневого узла. Рассмотрим длину путей, полученных с помощью маршрутов (1) и (2). Если route (1) создает более длинный путь, чем route (2), мы можем рекурсивно спускаться в каждое поддерево, содержащее путь этой длины, и запускать тот же процесс, чтобы идентифицировать ребра, которые потенциально могут быть использованы. Если route (2) создает более длинный путь, чем route (2), мы помечаем ребро от корня до каждого из его дочерних элементов, у которого самый длинный путь, начинающийся с корня поддерева, используется, и если есть ровно один таким поддеревом мы бы пометили каждое поддерево, связанное для второго по длине пути, как используемое. Затем мы рекурсивно спускаемся в эти поддеревья, всегда выбирая пути вниз по поддеревьям, содержащим один из многих возможных самых длинных путей.

Этот второй этап распространения занимает время O (n), поскольку каждый узел посещается ровно один раз, а выполненная работа пропорциональна количеству детей. В целом, это алгоритм времени O (n), который использует пространство O (n).