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