Найдем диаметры в обоих деревьях, если один из них больше $k$, то ответ 0. Иначе воспользуемся фактом, что для любой вершины в дереве наиболее удаленная вершина это одна из вершин диаметр. Тогда существует три варианта какой будет новый диаметр после проведения ребра $u,v$:

\begin{itemize}

\item Остался диаметр первого дерева

\item Остался диаметр второго дерева

\item Наиболее удаленная вершина от $u$ в первом дерева, ребро $u,v$, наиболее удаленная вершина от $v$ во втором дереве

\end{itemize}

Посчитаем для каждой вершины из обоих деревьев расстояние до наиболее удаленной вершины, найдя расстояния от обоих концов диаметра. Тогда нам нужно, чтобы при проведении ребра не появился диаметр $> k$. Для этого посчитаем число вершин в первом дереве, у которых максимальное расстояние до вершины в первом дереве $\le x$, для всех $x$. Это можем сделать префиксными суммами. Переберем второй конец ребра из второго дерева, пусть у него максимальное расстояние до другой вершины во втором дереве равно $x$, тогда нам подходят все вершины с максимальным расстоянием $\le k - x - 1$. Получили решение за $O(n)$.