#3-Coloring Problem for Tree with Some Pre-Colored Nodes I have a undirected tree and three colors to choose from. Some nodes are already colored; these nodes and their colors are given. What is an efficient algorithm to find the number of ways to color the rest of the nodes such that no two adjacent nodes are the same color?
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.