This part is about proper colorings. Any tree is connected bipartite graph. So when you color one vertex you can use either breadth-first search or depth-first search to color all other vertices, because when you push new vertex to a queue or stack you know the only appropriate color for it. Since you have only two possibilities to color the first vertex the time is linear, no DP is required.
This part is about maximum independent set. So after edit question become about maximum independent set (the set of blue vertices). For leave $v$ it is easy to see that there is maximum independent set $I_v$ that contains $v$. Really if some maximum independent set $I'$ doesn't contain $v$ than it should contain the only neighbor $u$ of $v$ because otherwise it is not maximal and therefore can not be maximum. Then $I_v = (I' \setminus \{\,u\,\}) \cup \{\,v\,\}$. Also if $\deg v = 0$ then $v$ obviously should be in each maximum independent set.
Therefore the algorithm is the following. Take arbitrary vertex of degree 0 or 1 leave color it into blue and remove this vertex from graph together with its neighbor if it exists. Continue while there are non-colored vertices. To make this approach efficient we can use queue (or stack) which contains all non-colored vertices of degree 0 or 1. Still no DP is required.
If DP is the only acceptable way then let's do the following. Do depth-first search (so the stack is required anyway). For each vertex $v$ compute the number of blue vertices in subtree of $v$ if $v$ is blue (number $f_b(v)$) and if $v$ is red (number $f_r(v)$). It is possible to compute it after computing for all children in the following way:
$$f_b(v) = 1 + \sum_{u \in N^+(v)} f_r(u),\\
f_r(v) = \sum_{u \in N^+(v)} \max\{\,f_r(u), f_b(u)\,\}.$$
This way also gives linear time.
