Question:
I have a tree $T$ with an even number of vertices $n$ and weighted edges. I want to divide the $n$ vertices into two disjoint subsets with same cardinality (i.e. $S, V-S, |S|=|V-S|=\frac{n}{2}$). such that it maximize the weight of the cut (i.e. maximizes $\sum w(u,v)$ where $u$ and $v$ are in two different sets).
My Attempt:
I've thought about a dynamic programming approach, namely define: $DP_{in}(u,k)$ as the max weight cut with $k$ vertices in set $S$ with a tree rooted at $u$ and with $u$ in $S$. Also, define $DP_{out}(u,k)$ as the max weight cut with $k$ vertices in $S$ of the tree rooted on $u$ but $u$ is not in $S$.
We are looking for $max(DP_{in}(root, \frac{n}{2}), DP_{out}(root, \frac{n}{2}))$. Also, I defined the recursion as:
$$DP_{in}(u,k)=\sum_{(u,v)}max(DP_{in}(v, k-1), DP_{out}(v, k-1)+w(u,v))$$ $$DP_{out}(u,k)=\sum_{(u,v)}max(DP_{in}(v, k-1)+w(u,v), DP_{out}(v, k-1))$$
However, I realized this doesn't account exactly for choosing $k$ vertices since if $u$ has two children, I may choose $k$ vertices in the cut for both of its children which would give me $2k$ vertices instead. I am not quite sure how I can control the size in the recursion.