資料結構與演算法

(5 points) In this problem we use the following notations. For any binary tree $T$, we define $T.x$ to be its root node, $T.l$ (resp. $T.r$) to be the left (resp. right) child of $T.x$, and $T.L$ (resp. $T.R$) to be the left (resp. right) subtree of $T.x$. For any vertex $x$ on a binary tree, we define $x.l$, $x.L$, $x.r$, and $x.R$ similarly. These values are defined as $\bot$ (empty) if they do not exist. The set of leaves of $T$ are denoted as $\mathrm{Leaf}(T)$. For any statement $P$ we define $\llbracket P \rrbracket$ to be $1$ if $P$ is true and $0$ if $P$ is false.

Let $T$ be a binary tree of $n$ nodes. Each node $v$ on $T$ has a weight $w(v)$ and a color $c(v)$. We want to make the tree colorful in the sense that every non-root tree node has a color different from its parent. To do so, some re-coloring to the tree nodes are necessary, and we would like to minimize the total weights of the tree nodes that are re-colored. Notice that there are infinitely many colors available so once a node is re-colored it gets a unique color. Let $f(T)$ be the answer. Suppose that both $T.L$ and $T.R$ are non-empty. What is the correct recursive formulations for $f(T)$? Select all choice(s) that apply.