Finding kth ancestor in log(n) time using Binary Lifting

help
, ,
1

I am trying to solve Kth ancestor using binary lifting

But i am getting WA.

Description:
We need to solve the kth ancestor method, GIven a root of a tree, we need to find the kth ancestor of node.

class Tree
        {
            int N=(int)1e4+5;
            
            int dp[][]=new int[N][31];
            int parent[]=new int[N];
            
            void dfs(Node root,int p) 
            {
                if(root==null)
                    return;
                parent[root.data]=p;
                dfs(root.left,root.data);
                dfs(root.right,root.data);
            }
            
            void construct(int u,int v)
            {
                dp[u][0] = v;
                for(int i=1;i<31;i++)
                {
                    dp[u][i]=dp[dp[u][i-1]][i-1];
                    if(dp[u][i]==-1)
                        break;
                }
            }
            
            public int kthAncestor(Node root, int k, int node)
            {
                for(int i=0;i<N;i++)
                    Arrays.fill(dp[i],-1);
                
                Arrays.fill(parent,-1);
                dfs(root,-1);
                for(int i=0;i<N;i++)
                {
                    if(parent[i]!=-1)
                        construct(i,parent[i]);
                }
                for(int i=30;i>=0;i--)
                {
                    if(((1<<i)&k)!=0){
                        node=dp[node][i];
                        if(node==-1)
                            break;
                    }
                }
                return node;
            }
        }

Can anyone explain where i am going wrong? Thank you :slight_smile: )
@everule1

2

I think the problem is that you are calling “construct” in increasing order of node value, but when you call for example construct(i, parent [i]) you need all the nodes from i to root have already been built. You can include that call in the dfs function

1 Like
3

Thank you :slight_smile:, yeah before we built the dp table, all its ancestors should have been built. I got the mistake. Will solve and get back to you.

4

My code still outputs WA, i have done what you told. I am unable to figure out:

                       class Tree
                    {
                        int N=(int)1e4+5;
                        
                        int dp[][]=new int[N][31];
                        
                        void construct(int u,int v)
                        {
                            if(v==-1)
                                return;
                            dp[u][0] = v;
                            for(int i=1;i<31;i++)
                            {
                                dp[u][i]=dp[dp[u][i-1]][i-1];
                                if(dp[u][i]==-1)
                                    break;
                            }
                        }
                        
                        void dfs(Node root,int p) 
                        {
                            if(root==null)
                                return;
                            construct(root.data,p);
                            dfs(root.left,root.data);
                            dfs(root.right,root.data);
                        }
                        
                        public int kthAncestor(Node root, int k, int node)
                        {
                            for(int i=0;i<N;i++)
                                Arrays.fill(dp[i],-1);
                            
                            dfs(root,-1);
                            for(int i=30;i>=0;i--)
                            {
                                if(((1<<i)&k)!=0){
                                    if(node==-1)
                                        break;
                                }
                            }
                            return node;
                        }
                    }
5

now you are doing nothing inside the last for loop, you should be updating what “node” is

6

Yeah a small typo. Thank you :slight_smile:

7

here is a problem on hackerrank.

my code :-

#include <iostream>
#include <vector>
using namespace std;
#define MaxN 100001

vector<vector<int> > tree, b_lift;
vector<bool> nodes;

void dfs(int a, int p) {
  b_lift[a][0] = p;
  for (int i = 1; i < 18; i++) {
    b_lift[a][i] = b_lift[b_lift[a][i - 1]][i - 1];
  }
  //cout << p << " -> " << a << " b : "; for (int& i : b_lift[a]) cout << i << ' '; cout << '\n';
  for (int& i : tree[a]) {
    dfs(i , a);
  }
}

void moveup(int &a, const int &k) {
  for (int i = 0; i < 18; i++) {
    if ((1LL << i) & k) a = b_lift[a][i];
  }
}

int main () {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int T; cin >> T;
  while (T--) {
    tree.resize(MaxN);
    b_lift.resize(MaxN, vector<int> (18, 0));
    nodes.resize(MaxN, false); nodes[0] = true;
    int N; cin >> N;
    int x, y;
    for (int i = 1; i <= N; i++) {
      cin >> x >> y;
      tree[y].push_back(x);
      nodes[x] = true;
    }
    dfs(0,0);
    int Q; cin >> Q;
    while (Q--) {
      int op; cin >> op;
      if (op == 0) {
        int a, b; cin >> a >> b;
        tree[a].push_back(b);
        dfs(b,a);
        nodes[b] = true;
      } else if (op == 1) {
        int x; cin >> x;
        nodes[x] = false;
      } else {
        int x, k; cin >> x >> k;
        if (nodes[x] == false) {
          cout << 0 << '\n';
          continue;
        }
        moveup(x,k);
        cout << x << '\n';
      }
    }
    tree.clear();
    b_lift.clear();
    nodes.clear();
  }
  return 0;
}

it is failing on 3 / 12 cases.