Suppose, there is a tree rooted at node 0. Initially counter is set to 1. There are three types of queries on this tree.
1 x - Add new node (counter number) to node x and increase counter.
2 x - delete node x, so the subtree of x will be deleted.
3 x - print count of nodes in subtree of x.
As an example, suppose following are the queries on tree.
1 0 - node 1 is added to node 0. now, counter = 2.
1 1 - node 2 is added to node 1. now, counter = 3.
1 0 - node 3 is added to node 0. now, counter = 4.
1 3 - node 4 is added to node 3. now, counter = 5.
1 4 - node 5 is added to node 4. now, counter = 6.
1 4 - node 6 is added to node 4. now, counter = 7.
1 5 - node 7 is added to node 5. now, counter = 8.
1 6 - node 8 is added to node 6. now, counter = 9.
3 6 - print total number of nodes in subtree 6
3 3 - print total number of nodes in subtree 3
2 5 - remove node 5 subtree.
1 2 - node 9 is added to node 2. now, counter = 10.
1 9 - node 10 is added to node 9. now, counter = 11.
3 1 - print total number of nodes in subtree 1
3 4 - print total number of nodes in subtree 4
Refer to the below image for the tree formation step by step according to queries.
Note - the number of type 1 queries <= 50000 and total number of queries <= 10^5.
Make a C++ program to efficiently process above queries.
Can someone please help me in solving this question?