  The automaton constrained tree knapsack problem is a variant of the knapsack
problem in which the items are associated with the vertices of the tree, and we
can select a subset of items that is accepted by a top-down tree automaton. If
the capacities or the profits of items are integers, the problem can be solved
in pseudo-polynomial time using the dynamic programming algorithm. However, the
natural implementation of this algorithm has a quadratic pseudo-polynomial
factor in its complexity because of the max-plus convolution. In this study, we
propose a new dynamic programming technique, called \emph{heavy-light recursive
dynamic programming}, to obtain pseudo-polynomial time algorithms having linear
pseudo-polynomial factors in the complexity. Such algorithms can be used for
solving the problems with polynomially small capacities/profits efficiently,
and used for deriving efficient fully polynomial-time approximation schemes. We
also consider the $k$-subtree version problem that finds $k$ disjoint subtrees
and a solution in each subtree that maximizes total profit under a budget
constraint. We show that this problem can be solved in almost the same order as
the original problem.
