Thats what I am not getting , but then is there a solution better than O(n^2)?
The intended solution was O(N+QK). Look at This comment. My first approach was naively checking if some node was ancestor of the other and that was worst-case O(N+NQ) and it TLEed. So O(N^{2}) solution passing is a surprise to me.
I was asking that for the LCM problem, all solutions look like O(n^2) to me
My bad, itâs really confusing here!!
Anyway, Iâve seen two types of solutions that passed LCM problem.
- Just check the adjacent. Which is completely wrong.
- Check for only the largest 100 or so distinct elements with the rest. Which is hard to argue! This doesnât TLE as far as I think.
But if just bruteforce has passed then itâs really sad!!
Even E and F were easier than this one 
I was doing this but it got TLE, basically I after finding node with minimum height, I cleared its daughters and did bfs downward from that min height node. If all k got reached, then I printed the min height node. But it is giving TLE, i guess its worst case O(NQ), how to improve this, without using the LCA method
I want to know the approach of Problem setter of this questionâŚwhat he thought before setting this problem and what us has intended solution
2 Likes
First make a dfs order and calculate the in time and out time for all nodes.Then for each query
sort the given list of vertices twice, once in increasing order of their in time and other on decreasing out time. if in both the cases the first element is same then output that else -1.
This works because the godfather must be an ancestor of all nodes and hence should satisfy ancestor descendant relation with all the other nodes.
2 Likes
Like I said, you can use In time and Out time to tell if a node is an ancestor of the other or not. What you did will TLE on bamboo-like trees.
Itâs a really easy trick and takes very little implementation: Here.
Basically you take note of when you are entering and exiting any node while dfs. Youâll enter the ancestor earlier than its children and leave later.
1 Like
I guess a counter example for second approach would be and array like this:
(assume array is sorted in ascending)
(211 is a prime and so is 103)
[..., 103, 1\cdot 211, 2\cdot211, ..., 100\cdot211]
In this case the LCM cannot be larger than 103\times100\times211, can it
Oh you wrote compare 100 elements with rest, my bad, I thought compare 100 among themselves.
1 Like
this solution seems to be best!