Если вы хотите решить сами - не читайте дальше, подсказки выше, вполне, достаточно.
Для каждой вершины при обходе в глубину надо найти максимальную U среди всех поддеревьев (т.е. LCA находится в поддереве) и случая когда LCA будет текущая вершина.
Для случая когда LCA - текущая вершина, возвращать самую глубокую вершину поддерева - достаточно.
Для случая когда LCA в поддереве, нам нужно знать минимум пару вершин и высоту с учётом ограничения по k.
Получается надо возвращать максимально глубокую и ответ для поддерева (v1, v2, h) с учётом ограничения по K.
Самым сложным было выделить 2 случая: когда LCA в поддереве и надо просто выбрать лучший результат и когда LCA - текущая вершина и надо найти наибольшую возможную высоту соответствующую ограничению по k.
В конечном итоге, вышло:
DFS(v, h) -> (h_max, v_max), (v1, v2, h_norm)
, где (h_max, v_max) - пара высоты и индекса вершины, для лексикографического сравнения и выделения 2х максимальных;
v1, v2 - пара максимальных вершин, которые нужно привести к высоте h_norm при выводе ответа;
v - текущая вершина;
h - текущая высота;
По-идее, достаточно просто v1, v2, h_norm, но в моей реализации было удобнее вернуть ещё 2 доп. значения. Да и я возвращаю, по-сути, 2 ответа. Первый использую для поиска ответа на задачу, а 2й для вывода результата.