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!