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 <[email protected]>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 --
