  The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data
structure for reporting $(s,t)$ mincuts (and by duality, the values of $(s,t)$
maxflows) for all pairs of vertices $s$ and $t$ in an undirected graph. Gomory
and Hu showed that it can be computed using $n-1$ exact maxflow computations.
Surprisingly, this remains the best algorithm for Gomory-Hu trees more than 50
years later, *even for approximate mincuts*. In this paper, we break this
longstanding barrier and give an algorithm for computing a
$(1+\epsilon)$-approximate Gomory-Hu tree using $\text{polylog}(n)$ maxflow
computations. Specifically, we obtain the runtime bounds we describe below.
  We obtain a randomized (Monte Carlo) algorithm for undirected, weighted
graphs that runs in $\tilde O(m + n^{3/2})$ time and returns a
$(1+\epsilon)$-approximate Gomory-Hu tree algorithm w.h.p. Previously, the best
running time known was $\tilde O(n^{5/2})$, which is obtained by running Gomory
and Hu's original algorithm on a cut sparsifier of the graph.
  Next, we obtain a randomized (Monte Carlo) algorithm for undirected,
unweighted graphs that runs in $m^{4/3+o(1)}$ time and returns a
$(1+\epsilon)$-approximate Gomory-Hu tree algorithm w.h.p. This improves on our
first result for sparse graphs, namely $m = o(n^{9/8})$. Previously, the best
running time known for unweighted graphs was $\tilde O(mn)$ for an exact
Gomory-Hu tree (Bhalgat et al., STOC 2007); no better result was known if
approximations are allowed.
  As a consequence of our Gomory-Hu tree algorithms, we also solve the
$(1+\epsilon)$-approximate all pairs mincut and single source mincut problems
in the same time bounds. (These problems are simpler in that the goal is to
only return the $(s,t)$ mincut values, and not the mincuts.) This improves on
the recent algorithm for these problems in $\tilde O(n^2)$ time due to Abboud
et al. (FOCS 2020).
