任务:

给出一个加权树图和一组节点对。对于每对(u,v)从集合,我需要找到(有效)最大边缘之间(U,V)。

我的方法:

对于每个对(u,v)使用Tayjon算法,我们可以找到最低的共同祖先LCA(u,v)=a。然后,我们可以给出(u,v)之间的路径(u,a)和(v,a)路径和最大(u,v)之间的最大边(最大值边(u,a),max x边(v,a))。

问题:

我试图在lca算法中添加max_edge save,但是还没有成功。

问题是: 如何在lca tarjan算法中添加对max edge save的支持?

我的尝试代码:

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]++;
    }
}

*对于每个节点,查询列表[node]由v组成,如(node,v)is needed pair。 我明白,我使用了双存储器(只是为了方便存取)。

我会感激任何提示或实现修复。