  We devise new cut sparsifiers that are related to the classical
sparsification of Nagamochi and Ibaraki [Algorithmica, 1992], which is an
algorithm that, given an unweighted graph $G$ on $n$ nodes and a parameter $k$,
computes a subgraph with $O(nk)$ edges that preserves all cuts of value up to
$k$. We put forward the notion of a friendly cut sparsifier, which is a minor
of $G$ that preserves all friendly cuts of value up to $k$, where a cut in $G$
is called friendly if every node has more edges connecting it to its own side
of the cut than to the other side. We present an algorithm that, given a simple
graph $G$, computes in almost-linear time a friendly cut sparsifier with
$\tilde{O}(n \sqrt{k})$ edges. Using similar techniques, we also show how,
given in addition a terminal set $T$, one can compute in almost-linear time a
terminal sparsifier, which preserves the minimum $st$-cut between every pair of
terminals, with $\tilde{O}(n \sqrt{k} + |T| k)$ edges.
  Plugging these sparsifiers into the recent $n^{2+o(1)}$-time algorithms for
constructing a Gomory-Hu tree of simple graphs, along with a relatively simple
procedure for handling the unfriendly minimum cuts, we improve the running time
for moderately dense graphs (e.g., with $m=n^{1.75}$ edges). In particular,
assuming a linear-time Max-Flow algorithm, the new state-of-the-art for
Gomory-Hu tree is the minimum between our $(m+n^{1.75})^{1+o(1)}$ and the known
$m n^{1/2+o(1)}$.
  We further investigate the limits of this approach and the possibility of
better sparsification. Under the hypothesis that an $\tilde{O}(n)$-edge
sparsifier that preserves all friendly minimum $st$-cuts can be computed
efficiently, our upper bound improves to $\tilde{O}(m+n^{1.5})$ which is the
best possible without breaking the cubic barrier for constructing Gomory-Hu
trees in non-simple graphs.
