узел на длинном расстоянии от другого узла в дереве

Question

Учитывая вход дерево, мы должны ответить на запросы типа,

a) данный узел указанного выше дерева, которое является узлом, который находится на самое длинное расстояние от этого узла.

b) удалить определенный набор ребер из дерева.

Я пытался это в течение долгого времени, но самое лучшее решением, которое я мог придумать было,

Для запроса типа a вызова dfs функции, которая будет возвращать дальний узел в O(N), но мне нужно сделать лучше. Для запроса типа b просто обновите дерево [remove edge if exists].

Таким образом, мое решение выше примерно O(K*N), где K - количество запросов, а N - количество узлов.

Answer 1

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

Идея заключается в том, чтобы найти «средний» из дерева, которое отделить дерево в деревья примерно одинакового размера, вызывая части произвольно, например, оставили и правой. Затем вы помечаете все узлы в своих соответствующих частях частью, в которой они находятся, и сохраняете левый и правый узлы, которые находятся дальше от середины. Когда вы получаете запрос для узла, вы просто смотрите на метку узла и сообщаете сохраненный узел с другой стороны.

Учитывая комментарий [и необоснованный нижний план], кажется, что решение требует немного большего объяснения. Во-первых, самый удаленный узел для данного узла, в общем, не является уникальным. Представьте себе, например, путь с ровно тремя узлами. Для среднего узла есть два самых отдаленных узла. Либо один из них является решением. Исходя из этого, идея состоит в том, чтобы найти узел в дереве, который расположен в середине пути между двумя самыми удаленными узлами в дереве (расстояние между этими узлами нечетно, можно выбрать узел с обеих сторон так что расстояния отличаются друг от друга на один): если самые удаленные друг от друга узлы имеют l узлов друг от друга, средний узел имеет путь длины l/2 к обоим из них или по пути l/2 к одному и л/2 + 1 к другому.

Используя этот средний узел, чтобы отделить дерево на две половинки, случайно называют покинул и право половина, позволяет определить дальнее кроме узла для любого заданного узла, если каждый узел знает, находится ли он в левую или правую половину: самый длинный путь будет проходить через средний узел в другую половину, а оттуда к узлу, наиболее удаленному от середины. Назовем длину самого длинного пути в левой части ll и длину самого длинного пути в правой части lr. Не нарушая общности, используйте lr < ll (просто поменяйте имена вокруг). Соответствующие самые удаленные друг от друга узлы от середины называются nl и nr.Обратите внимание, что это нормально, если есть несколько поддеревьев, ведущих из среднего узла, которые считаются частью правой части, если один из длинного пути (или самый длинный путь, если он уникален) находится в левой части.

Есть три случая, чтобы рассмотреть, когда вы хотите, чтобы указать дальний кроме узла от узла п:

1. Узел п является средним узлом. В этом случае наиболее удаленным узлом является, очевидно, nl.
2. Узел n находится в правой части дерева. Длинный путь можно построить путешествия по центру, а затем к нл, то есть узел, удаленный друг от друга, очевидно, нл тоже
3. узла п находится в левой части дерева. Опять же, самый длинный путь, который вы можете построить, перемещается в середину, но оттуда до nr.

Оставшийся вопрос только в том, как найти средний узел в O(n) время:

1. Найти все узлы листьев и положить их в очередь, маркируя их 1 и давая им расстояние 0. Это можно сделать в O(n) времени [и пробел].
2. Прочитайте (но еще не лишний) первый узел из очереди и найдите все соседние узлы. Если есть узел с меткой, которая меньше его количества соседних узлов, увеличьте метку. Если метка теперь соответствует количеству соседних узлов, добавьте узел в очередь и дайте ему расстояние, большее, чем первый узел из очереди.
3. Если в очереди есть только один узел, этот узел является средним узлом, и этот шаг завершается.
4. В противном случае извлеките передний узел и продолжите обработку очереди (т. Е. Шаг 2).

В качестве окончательного прохода найдите соседний узел с самой большой меткой расстояния и рассмотрите дерево, висящее на этом узле левым деревом. При маркировке узлов в качестве левых узлов BFS отслеживает последний узел в очереди, чтобы найти nl. Рассмотрим все остальные деревья поддеревья справа и назовите их с помощью BFS также в качестве правых узлов, также найдя nr.

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