Алгоритм разбиения дерева на компоненты связности

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

Ответ

Ясно, что для выполнения разбиения надо удалить ровно два ребра. Ясно также, что каждая компонента будет деревом. Также заранее ясно, чему будет равен суммарный вес вершин в каждом из трех поддеревьев. Пусть это будет Starget
Обозначим любую вершину дерева корнем и далее рассматриваем корневое дерево.
Будем строить наши связные компоненты путем наращивания (и объединения) множества поддеревьев снизу-вверх, от листьев к корню. Начинаем с набора стартовых поддеревьев, каждое из которых состоит из одной листовой вершины дерева. Если на каком-то этапе построения мы обнаруживаем поддерево T с суммой Starget, то существует решение, включающее поддерево T (если у задачи вообще есть решение). Все остальные варианты разбиения могут лишь "наращивать" T дополнительными вершинами, суммарный вес которых равен нулю. Будем назвать поддерево с суммой Starget завершенным Рассмотрим незавершенное поддерево T, корневая вершина которого являются сыном вершины P. Ясно, что P должно входить в одну и ту же связную компоненту, что и T. Из последнего утверждения сразу следует, что если у нас есть несколько незавершенных поддеревьев, корневые вершины которых являются сыновьями одного и того же предка P, то все они должны входить в одну и ту же связную компоненту, включающую также и P.
Отсюда автоматически следует, что решение задачи достаточно тривиально:
Начинаем с набора стартовых поддеревьев T, каждое из которых состоит из одной листовой вершины дерева. Циклически обрабатываем текущий набор поддеревьев T, пока у нас не останется ровно одно поддерево:     Если суммарный вес какого-то поддерева строго равен Starget (завершенное поддерево), то считаем его частью результата и исключаем из дальнейшего рассмотрения (исключаем из T и условно исключаем из исходного дерева).     Если в процессе такого исключения какая-то вершина исходного дерева становится листовой, то добавляем ее в T как отдельное поддерево.     Если у нас в T присутствуют все незавершенные поддеревья, чьи корни являются сыновьями некоей вершины P, то объединяем их в одно поддерево с корнем P. По завершению работы цикла 2-5 мы получим набор связных компонент, полученных на шаге 3, а также единственное оставшееся поддерево в T.     Если на шаге 3 получено ровно 2 завершенных поддерева, а вес оставшегося поддерева в T тоже равен Starget - то это наше решение.     Если на шаге 3 получено ровно 3 завершенных поддерева, а вес оставшегося поддерева в T равен нулю - то объединяем оставшееся поддерево с любым из завершенных и получаем решение.     В противном случае задача решения не имеет.