### pal_saab's blog

By pal_saab, history, 6 days ago,

we have given rooted tree , and target node and some other node A, we have to check if target node present in simple path from root to A , please tell me how to check this in o(1)

• -9

 » 6 days ago, # | ← Rev. 2 →   +5 $timein[x]$ is when you enter $x$ and $timeout[x]$ is when you leave $x$, these values can be calculated as below: t = 0; void dfs(u){ timein[u] = ++t; for(int v: adj[u]) if(!vis[v]) dfs(v) timeout[u] = ++t; }  If $a$ is an ancestor of $b$ only if this inequality is satisfied: $timein[a] ≤ timein[b] ≤ timeout[a]$. To check if some node $x$ presents in the simple path from root to $a$, it is enough to check if the root is an ancestor of $x$ and $x$ is an ancestor of $a$. We have to pre process in $O(n)$ then we can answer query in $O(1)$.
•  » » 6 days ago, # ^ |   0 Thanks
 » 5 days ago, # |   0 Could a O(logn) solution be that if LCA of target node and the given node A is target node itself, it is present. Else, it is not?
•  » » 5 days ago, # ^ |   0 You can also use LCA in $O(1)$ though
•  » » » 5 days ago, # ^ |   0 Oh...Great!!!!