# Question on graph queries

POST RESOLVED THANKS FOR YOUR COOPERATION

@everule1 this has to be done in O(nlogn) time complexity. can u suggest how can this be achieved in this question.

The constraints say otherwise but whatever/

Root the tree at E. Use O(N\log{N}) binary lifting precomputation to find LCA and another O(N) to find the depth of each node. Then removing the edge, which connects u and v, and without loss of generality, u is deeper than v, disconnects the subtree of u and the rest of the graph. If R does not lie in the subtree of u, we can get to E. To check whether A belongs to the subtree of B is equivalent to checking LCA(A,B)=B. If R lies in the subtree of u, we have to find the minimum distance to some node s\in S. For that we need some more precomputation.

We use a Dp on trees. Let dp_i denote the least distance of node i from a node s such that s\in S and s is in the subtree of i. dp_i=min(dp_c+w_{i,c}) for all c such that c is a child node of i where w_{i,j} denotes the weight of the edge from i to j. If i \in S, then dp_i=0. If there does not exist such a node s then dp_i=\infty.

Since the shortest path from any 2 nodes in a tree goes up and then down, it is the minimum distance of R from a node s\in S is min(dist_{R,i}+dp_i) for all i in the path from R to u. Now we can notice that dist_{R,i}=dist_{E,R}-dist_{E,i} since R is in the subtree of i with respect to E.
Therefore our answer is min(dist_{E,R} - dist_{E,i} + dp_i) = min(dp_i -dist_{E,i})+dist_{E,R}. We can find dist_{E,i} for all i in linear time. We can add a new feature to our binary lifting algorithm to also compute the minimum of dp_i-dist_{E,i} in the path. When we combine two values, we also take the minimum of dp_i-dist_{E,i} in the 2 paths. We can do the same while going up in the query algorithm to find the minimum in the path from R to u. And so we are done. If the minimum is \infty then there are no nodes in the subtree of u that belong to S.
The final time complexity is O(N\log{N}+Q\log{N}).

Kindly share the code