  The maximum/minimum bisection problems are, given an edge-weighted graph, to
find a bipartition of the vertex set into two sets whose sizes differ by at
most one, such that the total weight of edges between the two sets is
maximized/minimized. Although these two problems are known to be NP-hard, there
is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen
et al. (SIAM J. Comput. 2005) gave an $O(2^tn^3)$-time algorithm when given a
tree decomposition of width $t$ of the input graph, where $n$ is the number of
vertices of the input graph. Eiben et al. (ESA 2019) improved the dependency of
$n$ in the running time by giving an $O(8^tt^5n^2\log n)$-time algorithm.
Moreover, they showed that there is no $O(n^{2-\varepsilon})$-time algorithm
for trees under some reasonable complexity assumption.
  In this paper, we show an $O(2^t(tn)^2)$-time algorithm for both problems,
which is asymptotically tight to their conditional lower bound. We also show
that the exponential dependency of the treewidth is asymptotically optimal
under the Strong Exponential Time Hypothesis. Finally, we discuss the
(in)tractability of both problems with respect to special graph classes.
