Рыбий жир без ГМО

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

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

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

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

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