Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$. Is there a data structure that enables the immediate determination of membership of vertex $u \in V$? i.e., is $u\in V_1$?
Ideally a data structure with at most polynomial space complexity.
An example is as follows:
I have a tree that I will remove an edge from it to induce a forest of two tree components. Then, I want to attach another edge to reconnect the components to produce a new tree. This procedure is then repeated M times. I am looking for a data structure that enables this process to run in O(M) time.