Trouble understanding this dynamic programming solution
The problem is to count the subtrees of an undirected tree that have at
most k outgoing edges to the rest of the tree.

The idea of the algorithm is a divide and conquer plus dynamic programming technique. For a
tree T, you divide it into 2 subtrees, and for each you compute all
subtrees that have i outgoing edges for each i less than or equal to
k. There is however a little twist to allow the recurrence step to
work. The divide and conquer part is not really necessary, but it does allow a simpler organization.



I agree that the explanation of the algorithm that you were given is somewhat obfuscated.

small-boundary trees are what you called valid trees,  with at most
k out-going edges.

Consider your tree T.

Though in your undirected tree T all nodes are born equal, you choose
to distinguish a root v.

The idea is to count the number of subtrees for each value of the
number of outgoing edges, an also separate those that contain the root
v from those that do not.

Hence you have two vectors Tv+ and Tv--, for the subtrees including v and
for the subtrees not including root node v.
Tv+[i] is the number of subtrees including V that have i outgoing
edges.
Tv-[i] is the number of subtrees not including V that have i outgoing
edges.

The sum of these two vectors will give you the number of subtrees with i outgoing edges for each value of i less than or equal to k. At this point the distinction into two vectors has not been useful, but it is needed for the recursion.

Before using them, you have to compute these two vectors.

For that purpose, you choose an edge e={v,w}, which cuts your tree T in
two subtrees L and R, respectively rooted in v and w as shown on the figure

|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|


Suppose you have computed the vectors Lv+, Lv-, Rw+ and Rw-, then you
can use the results in those 4 vectors to compute Tv+ and Tv- as
explained in the document.

Subtrees that include v consist of a subtree in L that includes v,
plus optionally e and a subtree in R that includes w.

translates into :

Tv+[i] = Lv+[i-1] + sum (Lv+[j] * Rw+[k]) for all (j,k) such that j+k=i , for i&gt;0

Tv+[0] = 1    Only the whole tree T contains v and has no outgoing edges.

The i-1 in Lv+[i-1]is to account for the added outgoing edge {v,w}

The sum of products is for all subtrees that include the edge {v,w}, and thus have a
part in L and another in R.

Subtrees that don't include v consist of either a subtree in L that
doesn't include v, or a subtree in R (double counting the empty tree).

translates into :

Tv-[i] = Lv-[i] + Rw+[i-1] + Rw-[i]  for i>0

Tv-[0] = 1  for th empty tree {}

The i-1 in Rw+[i-1] is for the fact that subtrees counted in Rw+ get an extra edge {v, w} in the recurrence step since v is not included

There is empty tree in Lv-[i] and another in Rw-[i], but it does not matter as empty trees are considered  in the case i=0.

hoping I did not miss anything.

Is this enough to get you started, or do you need more?

One last point. The description of the algorithm starts by saying that it will consider the count of small-boundary trees, which I believe are your valid trees. If you know in advance the value of k (defining them) that you do not wish to exceed,
then you vectors need only have length k+1. For example, if k=1, the vectors should be of length 2 (for zero edges and for 1 edge). Any subtree that exceeds k edges will be useless for the rest of the algorithm (the count cannot go down)
and can thus be forgotten.

Note that, as described, the original algorithm uses variable size arrays, only as long as needed for the subtree at hand. That is required if you do not fix k in advance. If you do, you just use length k+1 as I said.

But this is a personnal remark that you may or may not trust. It is not in the algorithm you have been given.