Some days ago I was asked about the problem of finding least common ancestor of two given vertices. Specifically, the task is not to use any preprocessing of the tree, and a single LCA query should be answered in time O(r), where r is the distance between query vertices.

If there are no restrictions on memory usage, then the solution can be seen almost instantly: let's lift up both vertices simultaneously, and mark in two arrays all vertices visited during the first path and during the second path. As soon as we meet a vertex that is visited by both paths — this vertex will be the LCA.

But this solution requires O(n) memory, or, if we use hash-set, O(r) memory.

I started to think, is it possible to solve this problem almost without additional memory, i.e., use O(1) of memory. (Of course, the time complexity should remain the same O(r).)

And it turned out that yes, that's possible. Now I set this nice problem to you. (Possibly this is a known problem? I've never seen it before, though.)

As usual, post your solutions at comments, but hide them under edits, so that one can't read your solution accidentally.