Set partition refinement with subtrees

Question

In trying to design an algorithm, I needed a datastructure to implement a restricted kind of set partition refinement, where the sets $X$ to split on are subtrees. Specifically, given an arbitrary tree $T$ (computed earlier in the algorithm), and an initial partition where everything is in the same set, I need to do two things efficiently:

1. Refine the partition by splitting nodes in some subtree $T'$ of $T$ from the rest of the nodes.
2. Given a node $n$ in the tree, figure out the farthest (closest to the root) ancestor in its subset $S_n$.

The algorithm may have to do both up on (close to) every node on the tree, in any order. There's an obvious algorithm, similar to the one described on Wikipedia, where each node stores a pointer to the farthest ancestor in its set, and then when given a subtree $T'$ to split, we walk through every node in $T'$, and update the pointer to the root $r$ of $T'$ if it's an ancestor of $r$. The problem with this implementation is that since splitting can take up to $O(n)$ time (where $n$ is the size of the tree) to update all the pointers, the whole thing would be $O(n^2)$. Another implementation would be store, for each node, whether it's been split with its parent node. This makes splitting $O(1)$, since we just have to set the flag for the root node, but now finding the ancestor is $O(n)$ (we have to walk up the tree) so the whole thing is still $O(n^2)$. Is there a way to make this faster than $O(n^2)$ by taking advantage of the structure of the problem?