Given a tree with $$$N$$$ vertices, find the number of rooted trees (which consist of some edges present in the given tree) with $$$K$$$ vertices, including vertex 1. Constraints: $$$1 \leq K \leq N \leq 3000$$$.

Example :

Let $$$N$$$ = $$$5$$$ and the tree be this :

Then for K = 1, 2, 3, 4, 5 the solutions are :

This is probably a knapsack that runs in O(n^2) instead of the O(n^3) you expected. In case you want to overkill it use FFT.