Пусть мы знаем, сколько есть способов построить дерево с K крутыми(будем называть их так) фруктами для всех K. Тогда задача решается очевидным Meet-in-the-Middle. Научимся искать это число (назовем его f(K)).

Пусть у нас есть B горьких фруктов. Тогда построим граф, в котором вершины разделены на 3 типа: K вершин первого типа, B вершин второго и остальные — третьего. Проведем ребра между всеми парами вершин, кроме тех, в которых оба элемента пары принадлежат первому типу, либо один принадлежит первому, а второй — третьему. Найдем количество остовных деревьев в таком графе, посчитав соответствующий определитель (назовем это количество g(K)). Тогда посчитаем динамику:

.

Ну а дальше все просто.