I am a beginner so soory if the question sound too easy. If in the question it is given there are n cities and n-1 roads connecting them, solve something. The input is given as n (the number of cities) followed by n-1 roads (format u v meaning that there is a bidirectional road from u to v). How do I represent such a tree. I want a parent array to store the parent of each node. But how do I get the parent of each node assuming the root of tree is 1 always. An adjacency list stores for each vertex all the neighbouring vertices but it doesn't have any info about parent. Now if I want to find LCA in such a case, I need the parent array. So how to go about that. Thanks.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Apr/27/2024 06:20:52 (j3).
Desktop version, switch to mobile version.
Supported by
You need DFS. When you are at a node v and want to call dfs(u) , set parent[u] = v.
Thank you. I was reading finding LCA in O(n) preprocess time. So having DFS, can I say that it will become O(n+m) time? Is it correct?
Soory in tree m = n — 1 so total time is O(n). Thank you very much.
It's actually O(nlog(n)) since you need to calculate dp[v][i] (the 2i th ancestor of node v)
read this: [topcoder tutorial](https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Another%20easy%20solution%20in%20O(N%20logN,%20O(logN))
I am reading that article only. I was reading the method given above the method you suggested. It says <O(N),O(sqrt(N))>. Queryy time is more in this method so it should be better to use the one you suggest. Thanks
There are other methods for finding LCA. The way I read the post, it seems OP was referring to Tarjan's algorithm.