*Kth Ancestor

Kth Ancestor

A tree of P$P$ nodes is an un-directed connected graph having P−1$P-1$ edges. Let us denote R$R$ as the root node. If A$A$ is a node such that it is at a distance of L$L$ from R$R$, and B$B$ is a node such that it is at at distance of L+1$L+1$ from R$R$ and A$A$ is connected to B$B$, then we call A$A$ as the parent of B$B$.

Similarly, if A$A$ is at a distance of L$L$ from R$R$ and B$B$ is at a distance of L+K$L+K$ from R$R$ and there is a path of length K$K$ from A$A$ to B$B$, then we call A$A$ as the K$K$th parent of B$B$.

Susan likes to play with graphs and Tree data structure is one of her favorites. She has designed a problem and wants to know if anyone can solve it. Sometimes she adds or removes a leaf node. Your task is to figure out the K$K$th parent of a node at any instant.

Input Format 
The first line contain an integer T$T$ denoting the number of test cases. T$T$ test cases follow. First line of each test case contains an integer P$P$, the number of nodes in the tree. P$P$ lines follows each containing two integers X$X$ and Y$Y$ separated by a single space denoting Y$Y$ as the parent of X$X$. If Y$Y$ is 0$0$, then X is the root node of the tree. (0$0$ is for namesake and is not in the tree). 
The next line contains an integer Q$Q$, the number of queries. 
Q$Q$ lines follow each containing a query.

• 0$0$ Y$Y$ X$X$ : X$X$ is added as a new leaf node whose parent is Y$Y$ . X$X$ is not in the tree while Y$Y$ is in.
• 1$1$ X$X$ : This tells that leaf node X$X$ is removed from the tree. X$X$ is a leaf in the tree.
• 2$2$ X$X$ K$K$ : In this query output the K$K$th parent of X$X$ . X$X$ is a node in the tree.

Note

• Each node index is any number between 1 and 105 i.e., a tree with a single node can have its root indexed as 105

Output Format 
For each query of type 2$2$, output the K$K$th parent of X$X$. If K$K$th parent doesn't exist, output 0$0$ and if the node doesn't exist, output 0$0$.

Constraints 
1≤T≤3$1\le T\le 3$ 
1≤P≤105$1\le P\le {10}^5$ 
1≤Q≤105$1\le Q\le {10}^5$ 
1≤X≤105$1\le X\le {10}^5$ 
0≤Y≤105$0\le Y\le {10}^5$ 
1≤K≤105$1\le K\le {10}^5$

Sample Input

2
7
2 0
5 2
3 5
7 5
9 8
8 2
6 8
10
0 5 15
2 15 2
1 3
0 15 20
0 20 13
2 13 4
2 13 3
2 6 10
2 11 1
2 9 1
1
10000 0
3
0 10000 4
1 4
2 4 1

Sample Output

2
2
5
0
0
8
0

Explanation

There are 2 test cases. The first test case has 7 nodes with 2 as its root. There are 10 queries

• 0 5 15 -> 15 is added as a leaf node to 5.
• 2 15 2 -> 2nd parent of 15 is 15->5->2 is 2.
• 1 3 -> leaf node 3 is removed from the tree.
• 0 15 20 -> 20 is added as a leaf node to 15.
• 0 20 13 -> 13 is added as a leaf node to 20.
• 2 13 4 -> 4th parent of 13 is 2.
• 2 13 3 -> 3rd parent of 13 is 5.
• 2 6 10 -> there is no 10th parent of 6 and hence 0.
• 2 11 1 -> 11 is not a node in the tree, hence 0.
• 2 9 1 -> 9's parent is 8.

the second testcase has a tree with only 1 node (10000).

• 0 10000 4 -> 4 is added as a leaf node to 10000.
• 1 4 -> 4 is removed.
• 2 4 1 -> as 4 is already removed, answer is 0.

---------------------------------------------------editorial---------------------------------------

The naive approach for this problem is very obvious. Just store the parent of each node and find the kthparent by finding parent of each parent. But as the number of queries are large, this approach in the worst case (example: tree having only two leaf nodes) exceeds time limit.

The pick of the problem is that, instead of storing the parent of every node, we store all 2ith parent of a node i.e. 20th , 21st, 22th ... parent for each node.

Now for finding kth parent of a node A,

Let,
k = (bl-1bl-2....b0) in binary representation be a l-bit number k.

So k = b0 + b1 * 21 + ... + bl-2 * 2l-2 + bl-1 * 2l-1

Let s bits of these l bits are 1, p1,p2,...ps be indices at which bit value is 1.
k = 2p1 + 2p2 + ... + 2ps

Using above distribution of k, we can find kth node by following procedure.
A1 = 2p1th parent of A
A2 = 2p2th parent of A1, implies 2p1th + 2p2th parent of A
A3 = 2p3th parent of A2 which will also be 2p1th + 2p2th + 2p3th parent of A.

Similarly
As = 2psth parent of As-1 and also 2p1th+2p2th .... 2psth parent of A i.e. kth parent of A.

So it takes only s summations for finding kth parent. Since s is the number of bits in k. So this process takes O(s) = O(log k) time;

Now the problem is how to find 2i parents of each node?

Let parent[i][j] be 2jth parent of node i. Initially we know parent[i][0] i.e. first parent of all the nodes.

For j>0

parent[i][j] =  2^jth parent of i   
             =  (2^j-1th + 2^j-1th) parent of i   
             =  2^j-1th parent of (2^j-1th parent of i)    
             =  2^j-1th parent of parent[i][j-1]   
             =  parent[parent[i][j-1][j-1]  

The pseudo code is as follows

for i from 1 to n
    parent[i][0] = parent of i

for i from 1 to n
    for j from 1 to m
        parent[i][j] = parent[parent[i][j-1]][j-1]

In above code, m is the maximum value j can attain. In worst case, the highest value of parent a node can have is n-1.

2^m<=n-1
m = O(log n)

Hence above process takes O(n log n) time as well as O(n log n) space.

----------------------------------------------code---------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

list<pair<int,int> >li[100010];

lli dp[100010][30];

int lev[100010];

int dist[100010];

int dfs(int start,int par,int le)

{

  lev[start]=le;

  list<pair<int,int > >:: iterator it;

  for(it=li[start].begin();it!=li[start].end();it++)

   {

     if(it->first!=par)

      {

        dp[it->first][0]=start;

        lev[it->first]=le+1;

        dfs(it->first,start,le+1);

   }

   }

   

   return 0;

}

int binary_rais(int a,int k)

 {

   int lg;

   for(lg=1;(1<<lg)<=lev[a];lg++);

   lg--;

    // cout<<" lg "<<lg<<" k is "<<k<<endl;;

     for(int i=lg;i>=0;i--)

      {

        //cout<<i<<endl;

        if(k>=(1<<i)  && dp[a][i]!=-1)

          {

          k-=(1<<i);

            a=dp[a][i];

          }

          if(k==0) 

 {

  //cout<<" ret "<<a<<endl;

  return a;

 }

      }

      // cout<<k<<endl;

      return 0;

 }

int main()

{

// freopen("abc.txt","w",stdout);

 //freopen("pqr.txt","r",stdin);

int t;

cin>>t;

while(t--)

{

 

  for(int i=0;i<100010;i++) li[i].clear();

 int n;

 cin>>n;

 int sp;

 int mxid=0;

 for(int i=1;i<=n;i++)

 {

     int a,b,c;

    cin>>a>>b;

    mxid=(max(mxid,a));

    mxid=max(mxid,b);

    

    if(b==0) sp=a;

    else

    {

    li[a].push_back({b,c});

    li[b].push_back({a,c});

}

    

}

 memset(dp,-1,sizeof dp);

 

 dp[sp][0]=0;

  //cout<<" sp  is "<<sp<<" mxid is "<<mxid<<endl;

  

 dfs(sp,-1,1);

 // cout<<" dfs back";

    int max_h=25;//  or lon(n)

    //  maximum height 

    for(int i=1;i<=max_h;i++)

     {

       for(int j=1;j<=mxid;j++)

        {

            if(dp[j][i-1]!=-1)

            dp[j][i]=dp[dp[j][i-1]][i-1];

       }

     }

     

      //cout<<"ok";

     int q;

      cin>>q;

      while(q--)

      {

      int type;

      cin>>type;

      if(type==1)

       {

         int x;

          cin>>x;

          for(int i=0;i<25;i++)

               {

            dp[x][i]=-1;

            lev[x]=0;

}

}

else if(type==0)

{

int a,b;

cin>>a>>b;

dp[b][0]=a;

lev[b]=lev[a]+1;

for(int i=1;i<25;i++)

 {

  if(dp[b][i-1]!=-1)

  {

  dp[b][i]=dp[dp[b][i-1]][i-1];

  // cout<<" setting "<<(1<<i)<<" th par as "<<dp[dp[b][i-1]][i-1]<<endl;

 }

 

 }

}

else

{

// cout<<" in "<<endl;

 int a,k;

 cin>>a>>k;

 int ans=binary_rais(a,k);

 // cout<<ans<<endl;

 if(ans==-1) cout<<0<<endl;

 else

  cout<<ans<<endl;;

//    cout<<" out"<<endl;

}

 }

}

  return 0;

 }