PROBLEM LINK:Author: Gerald Agapov DIFFICULTY:HARD. PREREQUISITES:Heavylight decomposition,
Segment tree PROBLEM:There may be some differences between the original problem and the brief problem below, however, in fact we should only consider the brief problem below. QUICK EXPLANATION:For a given vertex x, our goal is to find the farthest white vertex y, y must be the ancestor of x or in the subtree of x or in the subtree of some light son of some ancestor of x. EXPLANATION:Firstly we implement the heavylight decomposition on the given tree. For convenience, we define that: Consider each heavy chain whose greatest ancestor is x, we construct a segment tree correspondingly. An interval [L,R] of the segment tree should store the information that In order to maintain the information above we need a heap for each vertex x which contains {distance(x,y)y is white and y is in the subtree of some light son of x}. As the segment tree has been constructed, we can get any information of every interval [L,R] online in O(logn) time. Now let's consider the query. For query0: Consider query vertex x. We change the color of x, and then update the information that this query influenced. If we change the color of vertex x, we should update the information of chain(x) at point interval rank(x) and for each vertex u which is the ancestor of x and chain(u)!=chain(x) we should update the information of chain(u) at point interval length(u). Notice that the number of different chain(u)s is O(logn) so this can be worked in O(log^2n) time. For query1: Consider query vertex x. In chain(x), we need the information of the intervals [0,rank(x)] and [rank(x),length(x)1]. For each vertex u which is the ancestor if x and chain(u)!=chain(x), we need the information of the interval [0,length(u)]. Notice that the number of different chain(u)s is O(logn) thus we can easily work out the distance between x and the farthest vertex from x in O(log^2n) time. There is a problem that we can only work out the farthest distance from some vertex x, not the very vertex we need to find. There is a trick: when we are calculating the distance between x and y, we return a pair(d,y) where d is distance(x,y) while y is the vertex's index. When we calculate max{a,b} where a and b are distances, if a.first!=b.first obviously we choose the greater one and if a.first==b.first max function can choose the distance with greater index vertex! Thus, we solve the problem in O(nlog^2n) time. ALTERNATIVE SOLUTION:There may be other ways to solve the problem, please share! AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here(Admin, please add). RELATED PROBLEMS:A very similar problem QTREE5. Enjoy it! asked 17 Dec '13, 18:10

Somebody please add the author's and tester's solutions.