Задача по теории алгоритмов "Функции".
Микросхема вычисляет функцию, значение которой зависит от других функций.
Функции, пронумерованы числами от 1 до N.
Указаны зависимости: для вычисления какой функции какие нужно знать. Получается дерево зависимостей между функциями (от данной функции может зависеть не более одной функции). Корень -- та функция, которую надо вычислить.
В микросхеме есть k ячеек памяти для промежуточных вычислений. Надо вычислить минимальное k и вывести порядок вычисления функций.
Пример: 1(2,3) 2(4,5,6) 3(7,8). Вычислить функцию номер 1.
Ответ: 3 ячейки (порядок 4:1, 5:2, 6:3, 2:1, 7:2, 8:3, 3:2, 1:1) (функция:скольно_ячеек_сейчас_занято).

Решение:
Рассматриваем все листья, ставим на на них пометки 1, добавляем в очередь всех родителей листьев.
Пока очередь не пуста, извлекаем из неё элемент, сортируем потомков этого узла по невозрастанию меток, вычисляем величину max(a[i]+i), где a[i] -- метка i-го потомка (нумеруются от 0). Эта величина и есть пометка данного узла (то есть сколько ячеек памяти нужно для вычисления этого поддерева). В очередь добавляем узлы, у которых рассмотрены все потомки.
Ответ: метка корня. Последовательность вычисления: обратный обход дерева(с учётом сортировки потомков).

Естественно, порядок вычисления неоднозначен.

Вопрос: Как вывести минимальный лексикографически порядок?
Основная проблема в том, что с этим дополнительным условием поддеревья уже не обязательно будут вычисляться оптимальным способом.
Пример: 10(9,8) 9(7,6,5,4) 8(3,1) 3(2). Ответ: (1:1, 2:2, 3:3, 8:1, 4:2, 5:3, 6:4, 7:5, 9:2, 10:1).
Поддерево 8 можно посчитать имея и лишь 2 ячейки памяти (2:1, 3:1, 1:2, 8:1), но мы должны считать за 3 из-за требования лексикографеской минимальности.

Может, кто-нибудь знает решение, полезные советы или книги, где это описано?