  In the \emph{$k$-Diameter-Optimally Augmenting Tree Problem} we are given a
tree $T$ of $n$ vertices as input. The tree is embedded in an unknown
\emph{metric} space and we have unlimited access to an oracle that, given two
distinct vertices $u$ and $v$ of $T$, can answer queries reporting the cost of
the edge $(u,v)$ in constant time. We want to augment $T$ with $k$ shortcuts in
order to minimize the diameter of the resulting graph.
  For $k=1$, $O(n \log n)$ time algorithms are known both for paths [Wang, CG
2018] and trees [Bil\`o, TCS 2022]. In this paper we investigate the case of
multiple shortcuts. We show that no algorithm that performs $o(n^2)$ queries
can provide a better than $10/9$-approximate solution for trees for $k\geq 3$.
For any constant $\varepsilon > 0$, we instead design a linear-time
$(1+\varepsilon)$-approximation algorithm for paths and $k = o(\sqrt{\log n})$,
thus establishing a dichotomy between paths and trees for $k\geq 3$. We achieve
the claimed running time by designing an ad-hoc data structure, which also
serves as a key component to provide a linear-time $4$-approximation algorithm
for trees, and to compute the diameter of graphs with $n + k - 1$ edges in time
$O(n k \log n)$ even for non-metric graphs. Our data structure and the latter
result are of independent interest.
