3
$\begingroup$

We are given a tree with n vertices and some of the vertices act as a "hotspot".

We have to answer multiple queries of type (a,b,c), which means we have to find the distance to the nearest hotspot from c such that we do not travel through the edge between nodes a and b.

I have tried many data structures like using lowest common ancestor and algorithms like mo's algorithm on a tree, I have also tried to process queries which are closer to root first, but none of these have given me the desired complexity for each query which is anywhere between O(1) to O(log(n)).

Is there any better algorithm or perhaps some clever precomputation(in less time than O(nlogn)) that can be used to solve this problem?

| cite | |
$\endgroup$