#3-Coloring Problem for Tree with Some Pre-Colored Nodes
Many problems on trees can be solved using dynamic programming. Let me explain how to solve a similar problem, independent set with fixed vertices. In this problem, you are given a tree $T$ and an independent subset $I$ of its nodes, and your task is to count all independent sets which contain $I$.

Arbitrarily root $T$ at some vertex $r \in T$. For every vertex $v \in T$, let $T_v$ be the subtree of $T$ rooted at $v$. For every $v \in T$, we will calculate two quantities:


$\alpha_v$ is the number of independent sets in $T_v$ containing $T_v \cap I$ and $v$.
$\beta_v$ is the number of independent sets in $T_v$ containing $T_v \cap I$ but not containing $v$.


We calculate these quantities recursively, as explained below, and output $\alpha_r + \beta_r$, which is the total number of independent sets in $T$ containing $I$.

The base case is when $v$ is a leaf. If $v \in I$ then $\alpha_v = 1$ and $\beta_v = 0$, and otherwise $\alpha_v = \beta_v = 1$.

Now suppose that $v$ is an internal node, say with children $v_1,\ldots,v_m$. If $v \in I$ then $\beta_v = 0$ and $\alpha_v = \prod_{i=1}^m \beta_{v_i}$, since an independent set containing $v$ cannot contain any of its children. If $v \notin I$ then it is still the case that $\alpha_v = \prod_{i=1}^m \beta_{v_i}$, and additionally $\beta_v = \prod_{i=1}^m (\alpha_{v_i} + \beta_{v_i})$, since we don't have any constraints on the $v_i$.

Now that the algorithm is laid out, you can check that it runs in linear time. Your problem can be solved in a similar fashion, also in linear time.