How can I get the path between two nodes if I've used LCA algorithm? What is the fastest way to get the smallest path between those nodes?

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3567 |

3 | tourist | 3520 |

4 | maroonrk | 3421 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3309 |

8 | Benq | 3283 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 194 |

2 | antontrygubO_o | 193 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | Radewoosh | 168 |

6 | tourist | 166 |

7 | Um_nik | 165 |

8 | ko_osaga | 163 |

9 | McDic | 162 |

9 | Ashishgup | 162 |

How can I get the path between two nodes if I've used LCA algorithm? What is the fastest way to get the smallest path between those nodes?

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/07/2020 10:16:05 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

smallest path between those nodesThere is only one path between any two nodes in a tree ... If your graph is not a tree, using LCA does not even makes sense.

How can I get the path between two nodes if I've used LCA algorithm?Let's say you want the path from node u to node v. Starting from node u, go to its parent, then its grandparent and so on until you reach LCA(u, v). Call this path p1. Do the same for v. Call the path p2. The path from u to v is just the union of p1 and p2.

Yes the graph is a tree for sure. But I've one question- Do i need to use LCA with binary lifting algorithm and simple LCA if I want to calculate the path between those 2 nodes? Which one will have better time complexity in calculating the path?

There are multiple ways you can compute LCA (you can google for those). Just pick one that suits you best.

codechef hmmmm i seee

Read this blog Algorithm Gym :: Graph Algorithms

Incase you have weighted graph: Use $$$dijkstra$$$, otherwise use $$$BFS$$$, no need to overcomplicate it.