Hi Danh , shouldn't be C will farthest leaf node from given A and B ? Thanks Shashank
On Sunday, January 13, 2013 7:43:23 AM UTC+5:30, Danh Nguyen wrote: > > Hi everyone, > > I'm trying to solve this problem, but I have no idea to > begin<http://discuss.codechef.com/questions/5069/tree-again#>. > I really need some hints for it: > > - > > Given a tree of N nodes, and Q queries. (1 <= N, Q <= 100,000) > - > > Each query has 2 arbitrary nodes on that tree (let's call them A and > B). > - > > We define that the distance from another node (let's say C) to A and B > is the minimum of {the distance from C to A, the distance from C to B}. > - > > To answer each query, find C so that the distance from C to A and B > are as large as possible. > > I don't think it's possible to do do each query in O(N). It should be > O(lgN). > > Please help me! Thanks a lot in advance! > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
