IOI 2003: как рассчитать узел с минимальным балансом в дереве?

Question

- это проблема Balancing Act , которая требует найти узел с минимальным балансом в дереве. Баланс определяется как:

Удаление любого узла из дерева получается лес : коллекция из одного или нескольких деревьев. Определите balance узла как размер самого большого дерева в лесу T, созданного удалением этого узла из T

Для дерева образцов, например:

2 6
1 2
1 4
4 5
3 7
3 1

Объяснение:

Удаление узла 4 приводит к двум деревьям, узлами-членами которых являются {5} и {1,2,3,6,7}. большее из этих двух деревьев имеет пять узлов, таким образом, баланс узла 4 равен пяти. Удаление узла 1 дает лес из трех деревьев одинакового размера: {2,6}, {3,7} и {4,5}. Каждое из этих деревьев имеет два узла, поэтому баланс узла 1 равен двум.

Какой алгоритм вы можете предложить для этой проблемы?

Спасибо

Answer 1

Я собираюсь предположить, что вы довольно долго рассматривали эту проблему: чтение решения не помогает, вы только лучше решаете эти проблемы, решая их сами .

Итак, нужно заметить, что вход - это дерево. Это означает, что каждый край соединяет 2 меньших дерева вместе. Удаление края дает 2 отключенных дерева (лес из 2 деревьев).

Итак, если вы вычислите размер дерева на одной стороне ребра, а затем на другой, вы сможете взглянуть на ребра узла и спросить: «Каков размер дерева на другой стороне?» этого края? "

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

Имея эти данные, достаточно перебрать все узлы, посмотреть на их ребра и спросить: «Каков размер дерева на другой стороне этого ребра?» Оттуда вы просто выбираете минимум.

Надеюсь, это поможет.

Answer 2

Вы в основном хотите проверить 3 вещи для каждого узла:

1. Размер его левого поддерева.
2. Размер его правого поддерева.
3. Размер остальной части дерева.(размер дерева - слева - справа)

Вы можете использовать этот алгоритм и расширить его до любого вида дерева (различное количество подузлов).

Перейти по дереву в последовательность в порядке .

Сделайте это рекурсивно:

Каждый раз, когда вы выполняете резервное копирование с узла на «родительский» узел, вам нужно добавить 1 + размер общих поддеревьев узла к «отец "узел.
Затем сохраните значение, назовем его maxTree , в узле, который содержит максимум между всеми его поддеревьями, и ((сумма всех поддеревьев) - (размер дерева).

Таким образом, вы можете вычислить все размеры поддерева в O (N) .
При обходе дерева вы можете хранить переменную, которая содержит минимумнайденное значение.