Let’s say we are given a rooted tree and we get only queries of type 2, then we can pre-process the tree and store the parent of each node. For answering any query, we just need to check two cases -

• Either both of the B and C has same parent.
• Parent of either of B and C has the other node as the parent.

Both of these cases can be easily checked by using stored parent.

Now the only thing remaining is how to maintain this rooted tree on the query of type 1. We use small-to-large merging, we maintain the size of the trees and always merge small to large one - process smaller tree and relabel parent for all nodes in it.

So all type 1 queries can be processed in O(NlogN) + O(Q) and all type 2 queries in O(Q).

Submission 53ms