Найти самый длинный путь между множеством узлов в дереве

Question

Недавно наткнулся на вопрос программирования.

Данное дерево может быть недвоичным, может быть одной цепью (или линейной) с N узлами.

На входе будет набор из K узлов, обозначенных a1,a2....ak. Я хотел бы найти самые длинные простые пути, которые начинаются с одного из этих K узлов и заканчиваются на одном из этих K узлов (отличается от начальных узлов). Логарифмический алгоритм, зависящий от N или K, должен соответствовать требованиям времени работы (например, KlogK, KlogN), если необходимо, должен быть в пределах моего желаемого лимита времени.

Спасибо

Answer 1

Может быть, вы можете попробовать этот подход -

1. Запустите DFS из любого узла, чтобы найти самый дальний конечный узел, назовем его узлом X.
2. Запустите другую DFS, чтобы найти самый дальний узел из X.
3. Путь, который вы нашли в шаге 2, является самым длинным путем в дереве.

Это должно работать для всех деревьев, а не только для двоичных деревьев.