Yet Another Xinversion

First find the euler path of the tree and then the rest of the problem is fairly easy. You can use a persistent segment tree to handle the update-query or you can just use the policy based data structures.