Hi Shashank, It could be. But if the tree has only 2 branches, and A, B lie as two leaf nodes on each branch, there won't be any more leaf position for C. Thus, C has to lie on the path between A and B. Could you give me some hint to find C in O(lgN) though?
On Mon, Mar 4, 2013 at 3:19 PM, BackBencher <shashank7andr...@gmail.com>wrote: > 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 algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
