  We consider global problems, i.e. problems that take at least diameter time,
even when the bandwidth is not restricted. We show that all problems considered
admit efficient solutions in low-treewidth graphs. By ``efficient'' we mean
that the running time has polynomial dependence on the treewidth, a linear
dependence on the diameter (which is unavoidable), and only a polylogarithmic
dependence on $n$, the number of nodes in the graph. We present the algorithms
solving the following problems in the CONGEST model which all attain
$\tilde{O(\tau^{O(1)}D)}$-round complexity (where $\tau$ and $D$ denote the
treewidth and diameter of the graph, respectively): (1) Exact single-source
shortest paths (actually, the more general problem of computing a distance
labeling scheme) for weighted and directed graphs, (2) exact bipartite
unweighted maximum matching, and (3) the weighted girth for both directed and
undirected graphs. We derive all of our results using a single unified
framework, which consists of two novel technical ingredients, The first is a
fully polynomial-time distributed tree decomposition algorithm, which outputs a
decomposition of width $O(\tau^2\log n)$ in $\tilde{O}(\tau^{O(1)}D)$ rounds
(where $n$ is the number of nodes in the graph). The second ingredient, and the
technical highlight of this paper, is the novel concept of a \emph{stateful
walk constraint}, which naturally defines a set of feasible walks in the input
graph based on their local properties (e.g., augmenting paths). Given a
stateful walk constraint, the constrained version of the shortest paths problem
(or distance labeling) requires the algorithm to output the shortest
\emph{constrained} walk (or its distance) for a given source and sink vertices.
We show that this problem can be efficiently solved in the CONGEST model by
reducing it to an \emph{unconstrained} version of the problem.
