This problem can be solved in $O(n^3)$ time, and it generalizes to graphs with constant treewidth [1].

Here we describe the dynamic programming solution for tree and also show the running time is $O(n^2)$. This is probably the solution in [1] when the input is a tree, so this might lead to $O(2^k{n}^2)$ time algorithm for graphs with treewidth $k$.

This problem can be reduced to the following problem by arbitrarily root the tree at a leaf, and replace each vertex with degree $d+1$ into a binary tree with $d$ leaves, and assign weight $0$ to the internal nodes (except the root) of the replacing binary tree, and infinite edge weight for the edges connecting internal nodes inside the binary tree.

Let $W(v)$ to be the sum of the vertex weights of the subtree rooted at $v$. Let $D(v,k)$ to be the subproblem of minimum cost partition of the the vertices of the tree rooted at $v$ into vertices $(A,B)$ such that $v\in A$ and ${\sum }_{a\in A}w(a)=k$. Assume $v$ have two children $u$ and $w$. There are 4 cases to consider, depending on which of $\{u,w\}$ is on the same side of the partition as $v$.

$$D(v,k)=\min \{\begin{array}{l}{\min }_{i}D(u,i)+D(w,k-w(v)-i)\\ {\min }_{i}w(vu)+D(u,W(u)-i)+D(w,k-w(v)-i)\\ {\min }_{i}w(vw)+D(u,i)+D(w,W(w)-(k-w(v)-i))\\ {\min }_{i}w(vu)+w(vw)+D(u,W(u)-i)+D(w,W(w)-(k-w(v)-i))\end{array}$$

Where $i$ taken over all the numbers that make sense. Other cases are similar and simpler. Note that $D(v,k)$ for a particular $k$ can be computed $O(k\min \{W(u),W(w)\})$ time. So computing $D(v,k)$ for all $1\le k\le W(v)$ takes $O(W(u)W(w))$ time.

Hence the running time would obey $T(n)\le {\max }_{a+b=n}T(a)+T(b)+O(ab)$. One can show $T(n)=O(n^2)$ is a solution by induction.

References