Всем доброго времени суток!

Много раз при решении задач на деревья (n ≤ 5000) я сдавал динамики в которых квадрат состояний и линия переходов, но если поставить нужный отсек, то динамика работает очень быстро. К примеру нужно нам посчитать количество деревьев таких, что ровно k вершин обладают нужным нам свойством. Я обычно пишу динамику (v, cnt) — решаем задачу для поддерева вершины v при k = cnt. Тупой переход в такой динамике делается за O(cnt) — заводим еще одну динамику по сыновьям и для текущего сына перебираем какое ncnt ≤ cnt мы отдадим ему. Так вот грубая оценка такой динамики O(nk²). Но на деле если поставить отсечение в переборе ncnt ≤ количество вершин в поддереве, то такая динамика будет работать очень быстро. Я слышал, что на самом деле асимптотика здесь O(nk). Умеет это кто-нибудь доказывать? Аналогичный вопрос если делать отсечение по количеству листьев в поддереве.