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

Straightforward Link/Cut Tree solution. Just dfs the input grid and build the tree graph represented by LCT; represent paths as bamboo splay trees: just make dfs-child the right child if turnout is good and do nothing otherwise. All parents in dfs-tree that do not satisfy turnout make path parents (see LCT terminology). Now each query is just a single access—sometimes called expose—operation that saves all path parents on the path.