$(20$ pts$.)$ Forest Trail Network. A park ranger provides you with a map of a forest trail network, repre$-$

sented as an undirected tree $T=(V,E)($in adjacency list format$),$ where each node corresponds to a specific

location $($e$.$g$.,$ a cafe$)$ along the trail and edges denote connections between locations. Furthermore, the

ranger designates a specific starting point rinV where all hikers commence their journey. It's crucial for the

ranger to efficiently determine whether one location can be reached from an "early checkpoint", meaning

that the path from the starting point $r$ to the location $v$ in $T$ passes through the early checkpoint $u.$ Addition$-$

ally, hikers should not visit a location more than once so they do not get bored. How can you preprocess the

trail map to allow the ranger to answer checkpoint queries of the form "can $v$ be reached by going through

checkpoint $u$ starting from $r$ without visiting locations more than once" in constant $O(1)$ time, with the

preprocessing itself taking $O(|V|)?$