GERALD2 - Editorial

liouzhou_101 · December 17, 2013, 6:10pm

PROBLEM LINK:

Author: Gerald Agapov
Editorialist: Tiny Wong

DIFFICULTY:

HARD.

PREREQUISITES:

Heavy-light decomposition,
Segment tree
To make the editorial more readable, we now introduce Heavy-light decomposition briefly.
For each vertex x which has at least a son, find the maximum size of the subtree of some son y of x, in case of a tie choosing any one vertex available is OK, we call y is the heavy son of x and we call p is the light son of x if p is not equal to y. That is, there is only one heavy son of x and the others are light sons. The edge between a vertex and its heavy son is called heavy edge, The edge between a vertex and its light son is called light edge.
Consider the sequence of vertex {a[0],a[1],a[2],…,a[m-1]}, for every i>0, a[i-1] is the father of a[i]. We call the sequence of vertex a heavy chain iff for every i>0, a[i] is the heavy son of a[i-1] and any edge connected to some vertex in the sequence is light edge.

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.
Given a rooted tree with N vertices, whose color is either white or black. You are asked to maintain M operations below:
0. Change the color of some vertex x. That is, change the color of the vertex to white if it is black and change the color of the vertex to black if it is white.

Find the farthest white vertex from a given vertex x. In case of a tie, choose the one with largest index.

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.
We implement the heavy-light decomposition on the given tree. On each heavy chain we construct a segment tree to store some information. Now for each vertex x, we should maintain a container which stores each distance between x and the vertex which is in the subtree of some light son of x.
Consider Query-0: When we change the color of some vertex x, we only need to change the information of O(logn) vertices due to the heavy-light decomposition.
Consider Query-1: For each query vertex x, our goal is to find some vertex u such that there’s a white vertex y in the subtree of u and LCA(y,x)=u and distance between x and y is maximal.
We can use a segment tree to maintain each heavy chain. Thus we can solve the problem in O(n log^2 n) time.

EXPLANATION:

Firstly we implement the heavy-light decomposition on the given tree.

For convenience, we define that:

distance(x,y) : distance between vertex x and vertex y.
chain(x) : the heavy chain which x is in.
from(x) : the greatest ancestor in chain(x).
chain(x,k) : the k-th vertex of chain(x), for example, chain(x,0)==from(x).
length(x) : the length of chain(x).
rank(x) : the rank of x in chain(x) such that chain(x,rank(x))==x.

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

max{distance(chain(x,L),u)|u is white and u is in the subtree of some light son of chain(x,k) where L<=k<=R} and
max{distance(chain(x,R),u)|u is white u is in the subtree of some light son of chain(x,k) where L<=k<=R}.

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 query-0: 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 query-1: 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).
Tester’s solution can be found here(Admin, please add).
Editorialist’s solution can be found here.