This question was asked recently in Google coding interview:

Design a tree-like data structure with two functionalities:

1. SetRoot(int nodeId): sets the root of the tree to the given Id node.
2. IsAncestor(int nodeId1, int nodeId2): return true/false if nodeId1 is ancestor of nodeId2.

Optimize DS for IsAncestor calls. Note that on calls of SetRoot, the connections direction may change.
I was asked to think of better time complexity than O(N), where N is no of nodes. Any ideas?