| Входной файл: | subtrees.in | Ограничение времени: | 2 сек | |
| Выходной файл: | subtrees.out | Ограничение памяти: | 256 Мб | |
| Максимальный балл: | 108 |
Дерево — это связный неориентированный граф без циклов. Поддеревом дерева T называется его связный подграф.
В зависимости от структуры дерева у него может быть несколько поддеревьев. Например, у дерева-цепочки из n вершин n(n + 1) / 2 поддеревьев, а у дерева-звезды (n − 1 вершина связаны с одной центральной) количество поддеревьев равно 2n − 1 + n − 1.
Аналогично может быть различное количество способов выделить в дереве два непересекающихся по вершинам поддерева, три непересекающихся поддерева, и т. д. Наконец, вне зависимости от структуры дерева есть 2n − 1 способ выбрать n − 1 непересекающееся поддерево и ровно один способ выбрать n непересекающихся поддеревьев (просто n изолированных вершин).
По заданному дереву с n вершинами выведите для каждого k от 1 до n количество способов выбрать k непересекающихся по вершинам поддеревьев данного дерева.
| № | Входной файл (subtrees.in) |
Выходной файл (subtrees.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|