Найти край максимальной цены между двумя узлами в дереве

Question

Задача:

Учитывая взвешенный граф дерева и набор пар узлов.Для каждой пары (u, v) из набора мне нужно найти (эффективно) максимальное ребро между (u, v).

Мой подход:

Использование алгоритма Тарьяна для каждой пары (u,v) мы можем найти младшего общего предка LCA (u, v) = a.Тогда мы можем представить путь между (u, v) как объединение (u, a) и (v, a) путей и максимальное ребро между (u, v) как max (max_edge (u, a), max_edge (v,a)).

Проблема:

Я пытаюсь добавить сохранение max_edge в алгоритме LCA, но пока не добился успеха.

Вопрос: Как добавить поддержку сохранения максимального края по алгоритму LCA Тарьяна?

Код моей попытки:

int max_cost;

int dsu_find(int node)
{
    if (node == parent[node])
        return node;
    max_cost = std::max(max_cost, edges[node][parent[node]]);
    return parent[node] = dsu_find(parent[node]);
}
void lca_dfs(int node, std::vector<std::list<int>> &query_list)
{
    dsu_make(node);
    ancestor[node] = node;
    marks[node] = true;
    for(auto neighbour:adjacency_list[node])
    {
        if (!marks[neighbour.first])
        {
            lca_dfs(neighbour.first,query_list);
            dsu_unite(node, neighbour.first);
            ancestor[dsu_find(node)] = node;
        }
    }
    for (auto query_node : query_list[node])
        if (marks[query_node])
        {
            dsu_find(query_node);
            dsu_find(node);
            printf("%d %d -> %lld\n", node, query_node,max_cost);
            query_list[query_node].remove(node);
            max_cost = 0;
        }

}

Но он работает неправильно.

Мойполная реализация lca (без некорректных модификаций):

std::vector<int> parent;
std::vector<int> rank;
std::vector<int> ancestor;
std::vector<bool> marks;
std::vector<std::list<std::pair<int, long long>>> adjacency_list;

void lca_dfs(int node, std::vector<std::list<int>> &query_list)
{
    dsu_make(node);
    ancestor[node] = node;
    marks[node] = true;
    for(auto neighbour:adjacency_list[node])
    {
        if (!marks[neighbour.first])
        {
            lca_dfs(neighbour.first,query_list);
            dsu_unite(node, neighbour.first);
            ancestor[dsu_find(node)] = node;
        }
    }
    for (auto query_node : query_list[node])
        if (marks[query_node])
        {
            printf("LCA of %d %d is %d\n", node, query_node,ancestor[dsu_find(query_node)]);
            query_list[query_node].remove(node);
        }

}
//dsu operations
void dsu_make(int node)
{
    parent[node] = node;
    rank[node] = 0;
}

int dsu_find(int node)
{
    return node == parent[node] ? node : parent[node]=dsu_find(parent[node]);

}
void dsu_unite(int node_1,int node_2)
{
    int root_1 = dsu_find(node_1), root_2 = dsu_find(node_2);
    if(root_1!=root_2)
    {
        if(rank[root_1] < rank[root_2])
            std::swap(root_1, root_2);
        parent[root_2] = root_1;
        if (rank[root_1] == rank[root_2])
            rank[root_1]++;
    }
}

* Для каждого узла query_list [узел] состоит из v такой как (узел, v) необходимая пара.Я понял, что использую двойную память (просто для облегчения доступа).

Буду благодарен за любые подсказки или исправления реализации.