I'm sorry. Maybe you don't get the question. Your method is used to find the nearest C to A and B, but we need to find C such that the distance from C to A and B are as *large* as possible.
Thank you for your response, I really appreciate that. And I'm looking forward to getting more ideas from you! On Wed, Jan 16, 2013 at 4:23 PM, rizwan hudda <rizwanhu...@gmail.com> wrote: > Root the tree at an arbitrary node and preprocess the tree using heavy > light decomposition. > For each query (A,B), find C = LCA(A,B) (It can be done in O(log n) time > now.), > now the required answer is min(level(A), level(B)) - level(C). > > > On Sun, Jan 13, 2013 at 7:43 AM, Danh Nguyen <danhnguyen0...@gmail.com>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! >> >> -- >> >> >> > > > > -- > Thanks and regards > Rizwan A Hudda > http://home.iitk.ac.in/~rizvan > > > > -- > > > --
