Гарри, Рон и Гермиона обнаружили, что чаша Пенелоппы Пуффендуй является крестражем. В результате встречи с Белатриссой Лестрейндж Гермиона узнала, что чаша находится в семейном хранилище Лейстренджей в банке Гринготтс.
Волшебный банк представляет собой дерево из n хранилищ, каждое из которых имеет тип, определяемый целым числом от 1 до m. Деревом называется неориентированный связный граф без циклов.
Хранилища с идеальной охраной имеют тип k, все хранилища с типом k имеют идеальную охрану.
В банке может быть не более x хранилищ с идеальной охраной.
Кроме того, если хранилище имеет идеальную охрану, все соседние хранилища не имеют идеальной охраны, а их тип строго меньше k.
Гарри хочет рассмотреть все возможные варианты устройства банка. Он знает расположение хранилищ, поэтому его интересует количество возможных вариантов назначить хранилищам типы, чтобы все условия выполнялись.
Примечание
В примере 1, не может быть хранилищ с идеальной охраной, так тип хранилища с идеальной охраной равен 1, что значит, что соседние хранилища должны иметь тип меньше чем 1, что невозможно. Поэтому единственно возможный вариант — когда все хранилища имеют тип 2.