  We present the first solution to $\tau$-majorities on tree paths. Given a
tree of $n$ nodes, each with a label from $[1..\sigma]$, and a fixed threshold
$0<\tau<1$, such a query gives two nodes $u$ and $v$ and asks for all the
labels that appear more than $\tau \cdot |P_{uv}|$ times in the path $P_{uv}$
from $u$ to $v$, where $|P_{uv}|$ denotes the number of nodes in $P_{uv}$. Note
that the answer to any query is of size up to $1/\tau$. On a $w$-bit RAM, we
obtain a linear-space data structure with $O((1/\tau)\log^* n \log\log_w
\sigma)$ query time. For any $\kappa > 1$, we can also build a structure that
uses $O(n\log^{[\kappa]} n)$ space, where $\log^{[\kappa]} n$ denotes the
function that applies logarithm $\kappa$ times to $n$, and answers queries in
time $O((1/\tau)\log\log_w \sigma)$. The construction time of both structures
is $O(n\log n)$. We also describe two succinct-space solutions with the same
query time of the linear-space structure. One uses $2nH + 4n + o(n)(H+1)$ bits,
where $H \le \lg\sigma$ is the entropy of the label distribution, and can be
built in $O(n\log n)$ time. The other uses $nH + O(n) + o(nH)$ bits and is
built in $O(n\log n)$ time w.h.p.

Data Structures and Algorithms