Please share implementations for finding the LCA by the method of Binary Lifting. Following one is mine, but I can't seem to figure out what is wrong with it.
int n;
int LOGN;
vector<int> adj[300005];
bool vis[300005];
int tin[300005],tout[300005],d[300005],p[300005];
int dp[300005][19];
vector<int> root;
int timer;
void calc()
{
LOGN=ceil(log2(n))+1;
timer=0;
for(int i=0;i<n;i++)
{
tin[i]=0;
tout[i]=0;
d[i]=0;
vis[i]=false;
for(int j=0;j<LOGN;j++)
{
dp[i][j]=-1;
}
}
}
void dfs(int v,int parent){
if(parent!=-1)
d[v]=d[parent]+1;
p[v]=parent;
tin[v]=++timer;
vis[v]=true;
dp[v][0] = parent;
for (int i = 1; i <= LOGN; ++i)
{
if(dp[v][i-1]==-1)
dp[v][i]=-1;
else
dp[v][i] = dp[dp[v][i-1]][i-1];
}
for(auto u : adj[v])
{
if(!vis[u])
{
dfs(u,v);
}
}
tout[v]=++timer;
}
bool is_ancestor(int u,int v){// is v ancestor of u?
if(tin[u]>=tin[v] && tout[u]<=tout[v])
return true;
return false;
}
int LCA(int u,int v){
if (is_ancestor(u, v))
return u;
if (is_ancestor(v, u))
return v;
for (int i = LOGN; i >= 0; i--) {
if (!is_ancestor(dp[u][i], v))
u = dp[u][i];
}
return dp[u][0];
}
void solve()
{
cin>>n;
rep(i,0,n)
{
int m;
cin>>m;
rep(j,0,m){
int child;
cin>>child;
adj[i].pb(child);
adj[child].pb(i);
}
}
calc();
dfs(0,-1);
int query;
cin>>query;
rep(i,0,query){
int u,v;
cin>>u>>v;
cout<<LCA(u,v)<<endl;
}
}









Here are my (basic) templates.
Binary Lifting
LCA
Thank you so much! If you don't mind, can you spot the mistake in my code?
In the lines
if (is_ancestor(u, v)) return u; if (is_ancestor(v, u)) return v;
it should be return v and return u respectively. You've returned it the other way around.
Thank you so much sir!
No problem! For future reference, when linking long code, either put it in a spoiler or use something like pastebin or IDEone (this is preferred), to stop your post from being annoying to read :) That might explain the downvotes on the post.
That is so kind of you! To have gone ahead and answered a genuine doubt inspite of most others downvoting it. I have nothing to do with this post, I was looking for something else but just accidentally chanced upon this. Thought I'd stop by and appreciate your kind gesture. You're awesome!