Задачка, кажущаяся на первой взгляд, переборной со сложностью
(N -- число вершин), может быть решена проще, быстрее, за полиномиальное время. Почему это так я хочу описать ниже.
Во-первых, кажущийся переборный алгоритм имеет место для произвольного графа (возможно есть оптимизации и можно решить быстрее). У нас же граф очень специфический. Он намного проще того, что есть в общем случае. Эта простота, например, выражается в отсутствии циклов.
Во-вторых, нам нужно разбить наш граф всего на 3 компоненты связности.
Теперь давайте обсудим: как это разбивать граф на компоненты связности. Мы сразу скажем, что разбиение на компоненты связности -- это удаление некоторых рёбер. Приведу пример разбиения на компоненты связности следующего графа:

Получим 2 компоненты связности:

Получим 3 компоненты связности:

Другой пример. Получим 2 компоненты связности (вершина 1 -- это заменена на вершину 15):

Получим 3 компоненты связности:

Как можно наблюдать, всегда при удалении 1 ребра, появляется ещё одна компонента связности. Это можно доказать срого. Но воздержимся, дабы не загружать текст. Таким образом, нужно удалить 2 ребра так, чтобы у нас оказалось 3 компоненты связности.
Давайте немного переформулируем задачу. Нам необходимо поставить 2 метки на рёбра так, чтобы в каждой компоненте оказался суммарный вес одинаковым. Что же для этого нужно сделать? ОЧЕВИДНО! Перебрать все пары рёбер. Для этого занумеруем их от 0 до N-1. Переберём все пары рёбер. И для каждой пары будем проверять: правильное ли у нас разбиение или нет. Напишем псевдокод:
# Перебираем все рёбра
for i in range edge:
for j in range edge:
# Если разбиение делит наше дерево на равные по весу части, то заканчиваем выполнение
if Splitting(i, j):
break
Очевидно, что сложность такого алгоритма будет полиномиальной
,
где g(n) -- время работы Splitting
.
Но что делаь с функцией Splitting(i, j)
? Очевидно, что Splitting(i, j)
может отработать за линейное время. Запустим из каждой вершины обход в глубину, причём, если в некоторой вершине мы уже были, то не будем туда заходить больше. Вот и получится, что мы обошли все вершины лишь по одному разу. Т.е. мы обошли каждую компоненту связности единожды. В таком случае, ассимптотическое время работы будет
, хотя, по факту, это будет 2N. Внутри DFS (обход в глубину) мы будем считать веса для каждой компоненты связности.
Время работы Splitting
можно улучшить следующим образом. Сделаем для этого предподсчёт. Для каждого ребра будем хранить 2 параметра: суммарный вес вершин выше ребра и суммарный вес ниже ребра. Приведём пример:

Т.е. для ребра, соединяющего вершины 15 (она же 1, см. выше) и 3, мы можем посчитать суммарный вес в каждом кластере. Делать это будем следующим образом. Запустим LR-обход дерева и для каждого ребра (Замечу, что рёбра можно ассоциировать с соответствующими вершинами. Например, ребро (11, 10) ассоциируем с вершиной 11, ребро (6, 2) ассоциируем с вершиной 6 и т.д. Далее будем говорить о вершинах, а не о рёбрах).
Продемонстрируем пример обхода:
0 - 10 - 11 - 12 - 13 - 15 (1) - 3 - 4 - 5 - 9 - 2 - 6 - 7 - 8
При обходе будем суммировать считать вес поддерева. Под весом поддерева будем разуметь сумму всех вершин. Пусть на i-ом шаге мы уже подсчитали вес поддерева с корнем в вершине v. Тогда нам необходимо перейти на уровень выше и посчитать вес поддерева более высокого уровня. Проиллюстрируем на рисунке ниже.

Пусть мы находимся в вершине 11. И для поддерева этой вершины мы уже посчитали вес (на рисунке она изображена листом, но будем считать, что у неё есть поддерево). Тогда нам необходимо перейти в вершину 10 и подсчитать вес поддерева вершины 10. В порядке LR-обхода, посетим и подсчитаем вес поддерева с корнем в вершине 12, 13. Тогда вес поддерева с корнем в вершине 10, будет суммой весов поддеревьев 11, 12, 13:

Имеем формулу в общем случае:

Для вершины v обозначим вес дерева выше неё:

ниже неё:

Теперь, нам нужно вычислить аналогично, для каждой вершины вес дерева выше неё. Для этого будем считать, что выше корневой вершины ничего нет. Тогда ещё раз запустим LR-обход (модифицированный). Модификация будет состоять в том, что мы будем осуществлять все действия ещё при спуске.
Очевидно, что данный алгоритм вычисления вышеуказанных характеристик отработает за время
.
Таким образом, для каждой вершины имеем вес дерева ниже неё и вес дерева выше неё.
Теперь нам необходимо научиться быстро узнавать: лежит ли данная вершина v в поддереве другой вершины u. Введём функцию:

Для её быстрого вычисления нам понадобятся дополнительные ухищрения. И ещё один предподсчёт.