  The weighted ancestor problem is a well-known generalization of the
predecessor problem to trees. It is known to require $\Omega(\log\log n)$ time
for queries provided $O(n\mathop{\mathrm{polylog}} n)$ space is available and
weights are from $[0..n]$, where $n$ is the number of tree nodes. However, when
applied to suffix trees, the problem, surprisingly, admits an $O(n)$-space
solution with constant query time, as was shown by Gawrychowski, Lewenstein,
and Nicholson (Proc. ESA 2014). This variant of the problem can be reformulated
as follows: given the suffix tree of a string $s$, we need a data structure
that can locate in the tree any substring $s[p..q]$ of $s$ in $O(1)$ time (as
if one descended from the root reading $s[p..q]$ along the way). Unfortunately,
the data structure of Gawrychowski et al. has no efficient construction
algorithm, limiting its wider usage as an algorithmic tool. In this paper we
resolve this issue, describing a data structure for weighted ancestors in
suffix trees with constant query time and a linear construction algorithm. Our
solution is based on a novel approach using so-called irreducible LCP values.
