У меня есть дерево из n узлов. Если я уберу k ребер этого дерева, у меня будет k + 1 новых деревьев, то есть лес из k + 1 деревьев. Как рассчитать количество узлов в каждом из этих новых сформированных деревьев?
Мне нужно сделать это для q запросов.
Мой подход:
Я могу удалить k ребер из исходного дерева и запустить dfs на каждом узле, из которого ребро было удалено, и найти размер нового дерева. А затем соедините узлы обратно после получения размера каждого дерева.
Но это не оптимально, может кто-нибудь предложить лучший подход.