This blog is about problem 3 from this blog.

*Given a tree T of N nodes and an integer K, find number of different sub trees of size less than or equal to K.*

This is a very useful problem in the whole world of cp. The solution given in that blog is *O*(*n* * *K*^{2}) but we want to change it to *O*(*n* * *K*).

Consider *Sub*_{v} as the size of the subtree of vertex *v*.

The solution is similar to the given solution in that blog and the difference is very simple. You don't have to iterate over all *K* values. It's obvious that if *i* > *Sub*_{v} then *dp*[*v*][*i*] = 0. So each time you have to iterate over *min*(*K*, *Sub*_{v}) values.

The code becomes like this.

**The Code**

#### The Proof Of The Complexity

First we introduce the array *EnterTime*. If *EnterTime*_{v} = *x* then *v* is the *x*'th vertex we have entered to solve. Every vertex has a *st*_{v} which is an array and in the very beginning *st*_{v} = {*v*} for all *v*. We'll change this set later and I'll explain how. **Also consider st_{v} always sorted by EnterTime.**

We want to build a digraph *H* of size *n*. When we're about to update *dp*[*v*] from its child *u*, add a directed edge from every vertex is *st*_{u} to every vertex in *st*_{v} in the digraph *H*.

Then update *st*_{v} by adding the first *K* - *size*(*st*_{v}) vertices from *st*_{u}. (If *size*(*st*_{v}) = *k* then ignore this) Also erase every vertex from *st*_{u}.

The complexity is equal to number of edges of *H*. We want to prove that number of edges in *H* is at most *n* * (2 * *K*) by proving that every vertex in *H* has at most 2 * *K* edges going out from it.

By our definition at any time, for any vertex *v* there's at most 1 vertex *u* such that *v* is in *st*_{u}. Consider some *w*'s last set is *st*_{u} and we're about to update *dp*[*v*] from its child *u*. Consider *w* being in the *p*'th position in *st*_{u}. By our definition edges that go out of *w* are edges to the first *p* - 1 vertices in *st*_{u}.

We know that *p* ≤ *K* so until now, edges going out from *w* are at most *K*. When we're updating *dp*[*v*] we'll add at most *K* to that number. So by far *w* has at most 2 * *K* edges going out from it. Also we've considered *st*_{u} to be the last set that *w* is in. Hence there won't be any other edges going out from *w* in the future.

So we have proved number of edges in *H* is at most *n* * (2 * *K*) so the complexity is *O*(*n* * *K*).