Minimum graph cut with constraints
The problem that you describe is NP-hard even on stars as we can reduce Multicut in Trees to its decision version (where we have a cost bound). In Multicut in Trees the input is a tree $G=(V,E)$, a set $S\subseteq {V\choose 2}$ of vertex pairs, and an integer $k$ and one asks whether one can separate all vertex pairs of $S$ by removing at most $k$ edges. The reduction to your problem is to keep $G$ and $S$ as they are, set $N$ to $k+1$ and set the cost bound for accepting a solution to $+\infty$. Then the Multicut instance is a yes-instance if and only if the constructed instance is a yes-instance.

Note that this reduction does not specify how to define the edge weights. In other words, even testing whether there is a feasible solution, that is, any partition with $N$ parts is NP-hard.