Я считаю, что ответ - 1 или 2. Таким образом, не более 2 разных MHT. Эта проблема эквивалентна первому нахождению диаметра данного графа. Диаметр дерева - это максимальная длина пути между двумя узлами дерева.
Существует очень элегантный двухпроходный алгоритм для определения диаметра дерева.
- выберите произвольный узел A и найдите самый дальний узел B от A. (используйте поиск в глубину или поиск на вдохе).
- Начните с узла B, выполните второй DFS или BFS, чтобы найти самый дальний узел C от B. Расстояние между B и C - это диаметр этого дерева.
Имея информацию о диаметре, мы можем фактически получить root узлов этих MHT. Если диаметр четный, то будет только 1 MHT, а его root - средний узел пути от B к C; Если диаметр нечетный, то будет 2 MHT, а корни будут средними 2 узлами пути B к C. Эти 2 root узла гарантированно будут смежными друг с другом.
Следующая ссылка показывает доказательство количества центров дерева. Ключевым моментом в этой проблеме является то, что мы хотим использовать центр дерева как root, поскольку это обеспечивает общую минимальную длину пути ко всем остальным узлам. Вы можете доказать это противоречием: использование любых других узлов приведет к увеличению высоты дерева.
https://en.wikipedia.org/wiki/Centered_tree#: ~: text = A% 20graph% 20can% 20have% 20an, two% 20centers% 20 (с двумя центрами% 20 деревьев) .