URAL 1699 - Turning Turtles

Problem
Given a W x H map where the passable cells form a tree. Q queries: what is the number of turns required travelling from cell (x1, y1) to (x2, y2)?

W x H ≤ 100000
Q ≤ 50000

Solution
Obviously it is a LCA problem. However, the problem is the weight of edges depend on 3 nodes (not 2). Assign weight[u][v] =

1 if parent[u], u, v is a turn
0 else

For Query(x,y), find z = LCA(x, y). Then find 2 children of z, x' and y', such that the path is x->x'->z->y'->y. The answer is sum[x]-sum[x']+sum[y]-sum[y']+IsTurn(x',z,y'). Special handle the case x or y = z.

I implemented a dfs to pre-process the tree for LCA queries. However it will cause stack overflow. Therefore I implemented a non recursive version tree traversal, using stacks. So complicated..