Weight of heaviest edge in the path between two nodes in a Tree

claporslap's blog

By claporslap, 8 years ago, In English

How can I calculate this with efficiency without using HLD or Link Cut Trees? I tried doing it with Binary Lifting but I am not able to do it correctly. Please guide me. Thanks.

#graph, dfs and similar, #dp, #trees

claporslap
8 years ago
1

Comments (1)

Write comment?

ivanilos

8 years ago, hide # |

+14

You are in the right path if you tried doing it using binary lifting. Have you managed to succeed in doing a regular binary lifting (just to find the LCA of 2 vertices)? If not I recommend you reading this blog

Now, if you understand how to find LCA of 2 vertices, you do almost the same thing you did for calculating the parenting array but instead you do it for the length of edges

pre-process example

// g is the adjacency list

// w is the "adjacency list" of weights

void DFS(int node, int cost, int par = -1) {

p[node][0] = par;
maxi[node][0] = cost;

if (par != -1) {
    h[node] = 1 + h[par];
}

for (int i = 1; i < MAX_LOG; i++) {
    if (p[node][i - 1] != -1) {
        p[node][i] = p[p[node][i - 1]][i - 1];
        maxi[node][i] = max(maxi[node][i - 1], maxi[p[node][i - 1]][i - 1]);
    }
}

for (int i = 0; i < (int)g[node].size(); i++) {
    int viz = g[node][i];
    if (viz != par) {
        DFS(viz, w[node][i], node);
    }
}

}

For a query it is again very similar to finding the LCA of 2 vertices.

→ Reply