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

Даны взвешенный граф дерева и набор пар узлов. Для каждой пары (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, а)).

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

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

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) необходима пара.
Я понял, что использую двойную память (просто для облегчения доступа).

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