The idea is to use recursion. Let us suppose that the children of the root $r$ are $v_1,\ldots,v_d$, and let $S_1,\ldots,S_d$ consist of those elements of $S$ in the subtree rooted at $v_1,\ldots,v_d$, respectively.
One easy case is when $r \notin S$ and $|S_i|$ is even for all $i$. In this case, we can simply recurse on the subtrees. There are two complications that arise in the general case:
- Some $|S_i|$ might be odd.
- The root might belong to $S$.
The two complications are related, but let us tackle them one by one. Suppose first that $r \notin S$. If $|S_i|$ is odd for some $i$, then we would like to fix that. The only reasonable way is to add $v_i$ to $S_i$ if $v_i \notin S_i$, and to remove $v_i$ from $S_i$ is $v_i \in S_i$. We now solve the modified problem recursively, and have to somehow derive a solution for the original problem.
Let us introduce some notation: $O$ is the set of $i$ such that $|S_i|$ is odd, and $S'_i$ is the set $S_i$ after modification (adding or removing $v_i$). Consider a solution for the new instance. We will derive a solution for the original instance by pairing up the indices in $O$. Suppose that we chose to pair $i,j$, and consider the solutions for $S'_i,S'_j$. There are three cases to consider:
- $v_i \in S_i$ and $v_j \in S_j$. In this case we add a path from $v_i$ to $v_j$ via $r$.
- $v_i \notin S_i$ and $v_j \notin S_j$. In this case we add a path from $v_i$ to $v_j$ and "erase" $v_i,v_j$. That is, in the solution to the new problem, $v_i$ is connected to some $w_i$ in its subtree, and $v_j$ is connected to some $w_j$ in its subtree. We connect $w_i$ and $w_j$ via the path $w_i-v_i-r-v_j-w_j$.
- $v_i \in S_i$ and $v_j \notin S_j$. In this case we add a path from $v_i$ to $v_j$ and "erase" $v_j$. That is, in the solution to the new problem, $v_j$ is connected to some $w_j$ in the subtree. We connect $v_i$ and $w_j$ via the path $v_i-r-v_j-w_j$.
When $r \in S$, we only have to modify the above strategy a little. We arbitrarily pair $r$ with some $i \in O$, and then proceed much as above. This time there are only two cases:
- $v_i \in S_i$. In this case we simply connect $r$ and $v_i$.
- $v_i \notin S_i$. In this case we add the edge between $r$ and $v_i$ and "erase" $v_i$. That is, in the solution to the new problem, $v_i$ is connected to some $w_i$ in its subtree. We connect $r$ and $w_i$ via the path $r-v_i-w_i$.