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 <[email protected]>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 [email protected]. > 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 [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
