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 | tourist | 3985 |
| 2 | jiangly | 3741 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3442 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 2 | atcoder_official | 162 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | nor | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/19/2024 15:30:04 (j1).
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.