TREE AGAIN!

Hi everyone,

I’m trying to solve this problem, but I have no idea to begin. 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!

//