I am facing an error in solving the Question from SecondThread's gym on Tree basics. Since, I cannot view the testcases where my code is failing, I need some help. I also cannot see other's solution because you need >1900 rating. Can someone share their solution in C++ or point out the mistake in my code? I promise that the code is quite readable.
CODE:
int LOGN = 19;
int n;
int timer = 0;
vector<int> adj[300005];
bool vis[300005];
int p[300005], tin[300005], tout[300005];
vector<int> d(300005,0);
int dp[300005][20];
void dfs(int v, int parent)
{
tin[v] = ++timer;
if (parent != -1)
d[v] = d[parent] + 1;
p[v] = parent;
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 (u != parent)
dfs(u, v);
}
tout[v] = ++timer;
}
bool isAncestor(int p, int c){ // check if p is ancestor of c
return (tin[p] <= tin[c] && tout[p] >= tout[c]);
}
int lift(int v, int steps) //find the y-th ancestor of x
{
for (int i = 0; i < 19; ++i){
if ((1 << i) & steps){
v = dp[v][i];
if (v == -1)
return -1;
steps -= (1 << i);
}
}
return v;
}
int LCA(int u, int v)
{
if (isAncestor(u, v))
return u;
if (isAncestor(v, u))
return v;
for (int i = 18; i >= 0; i--)
{
if (dp[u][i] == -1)// -1 should not be passed
continue;
if (!isAncestor(dp[u][i], v))
u = dp[u][i];
}
return dp[u][0];
}
void solve()
{
cin>>n;
timer=0;
for(int i=0;i<n-1;i++){// Input
int x,y;
cin>>x>>y;
x--;y--;
adj[x].pb(y);
adj[y].pb(x);
}
dfs(0,-1);
tout[0]=++timer;
int q;
cin>>q;
for(int z=0;z<q;z++){
int u,v,energy;
cin>>u>>v>>energy;
u--;v--;
if(isAncestor(u,v))// u is ancestor of v
{
if(d[v]-d[u]<=energy)// reachable
cout<<v+1<<endl;
else{// midway: lift
int res=lift(v,energy);
cout<<res+1<<endl;
}
}
else if(isAncestor(v,u))// v is ancestor of u
{
if(d[u]-d[v]<=energy)// reachable
cout<<v+1<<endl;
else{/// midway: lift
int res=lift(u,d[u]-d[v]-energy);
cout<<res+1<<endl;
}
}
else{
int lca=LCA(u,v);
int dist=d[u]+d[v]-2*d[lca];
if(energy>=dist)
cout<<v+1<<endl;
else{
// find vertex of the path from u to v with distance of energy from u
int dist1=d[u]-d[lca];
int dist2=d[v]-d[lca];
// lies on the path from u to LCA
if(energy<=dist1){
int res=lift(u,energy)+1;
cout<<res<<endl;
}
// lies on the path from LCA to v
else{
int rem=energy-dist1;
dist2-=rem;
int res=lift(v,dist2)+1;
cout<<res<<endl;
}
}
}
}
}
signed main()
{
FAST;
solve();
return 0;
}
