Hint

For each vertex in tree find the nearest vertex from the way to root, in which we need to change direction. If such vertex doesn't exist, let it be -1. Let's call this vertex as bad[V], where V - some vertex in tree.

To answer on query for vertex X, let's travel in "bad" array from X until we meet bad[X]=-1. Let's save visited vertices (excluding query vertex X) to some array (let's call this array "change"). Now it's quety obvious, that we need to change directions only in those visited vertices to "activate" path from root to leaf. Before changing values in "bad" array for vertex from X to root, let's take some vertex V from "change" array. Before query there was a set of vertices which have the same "bad" vertex as a V (bad[V]=bad[V_1]=bad[V_2]=...=bad[V_n], V_i - vertex from the set), and now we need to change their "bad" value to V, because we change direction in vertex V.

Finally, we need to set bad[V]=-1 to all vertices from X to root.

To do all operations efficiently we can use heavy-light decomposiotion + segment tree. So, the total complexity would be O(N + Q*(log(N))^2), N - number of vertices in tree.

*Edited by author 06.06.2019 17:11*