Блог

Моя задача — эффективно обрабатывать Q запросы в графе связующего дерева с N узлами.

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

Моя текущая идея состоит в том, чтобы запустить DFS с двух узлов, соединенных этим ребром, убедившись, что DFS никогда не пересекает само ребро. Таким образом, я смогу найти размеры двух компонентов за O(N) время для общей сложности O(Q * N) .

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

Ну, вот стратегия, которую я только что придумал:

Во-первых, найдите любой узел, который имеет степень точности 1 (который гарантированно существует в графе связующего дерева; он называется «лист»). Запустите DFS с этого узла, сохраняя переменную count , представляющую количество узлов, которые были посещены до сих пор. Каждый раз, когда вы пересекаете ребро, размер двух компонентов, образованных удалением этого ребра, должен быть равен count и N - count из-за особых свойств дерева (в частности, между любой парой узлов есть ровно один путь). В результате получается алгоритм с O(N) предварительной обработкой и O(1) ответом на запрос, общая временная сложность которого составляет O(N Q) .