# Marathon on tree , Help required, Graph problem 9 [solved]

Question : “https://www.codechef.com/problems/MOAT

My solution : “https://www.codechef.com/viewsolution/36193665

Check whether a node “r” is in the path from vertex “u” to “v”

Are you asking why it’s TLE, or how to optimize it?

How is this possible I saw two solutions -

1st -

If there is node “r” exist from path “x” to “y” then

distance from x to y >= distance from x to r + distance from r to y

``````while(q--){
scanf("%d%d%d",&x,&y,&r);
int dxy = h[x]+h[y]-2*h[lca(x,y)];
int dxr = h[x]+h[r]-2*h[lca(x,r)];
int dry = h[r]+h[y]-2*h[lca(r,y)];
if(dxy<dxr+dry){
printf("NO\n");
}
else{
printf("YES\n");
}
}
``````

2nd -

``````while(q--)
{
cin>>st>>end>>val;
st--;
end--;
val--;
ll vall = LCA(st,end);
if((LCA(val,st) == val || LCA(val,end) == val) && LCA(vall,val) == vall)
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
}
}
``````

@galencolin how this is true ?

No need to reply , Thanks I did

``````while(q--)
{
lli x,y,r;

cin>>x>>y>>r;

// If there is node “r” exist from path “x” to “y” then

// distance from x to y == distance from x to r + distance from r to y

lli dist_x_to_y = getDistance(x,y);

lli dist_x_to_r = getDistance(x,r);

lli dist_r_to_y = getDistance(r,y);

if(dist_x_to_y == (dist_x_to_r + dist_r_to_y))
print("YES");
else
print("NO");
}
``````
1. visualize the path from x to y, and overlay the paths from r to x and r to y. If r is not on on the path from x to y, then at least one vertex that isn’t r will be visited by both of r's paths to x and y, and thus some distance will be “wasted”. But if r is on the path, then that won’t be true and the total distance will be exactly d(x, y).

2. this just checks if lca(x, y) is a parent of r and r is a parent of either x or y

1 Like