T at the speed of 1 edge per second. (i.e. Assuming that the path from. T, Eva will stay still there until she is caught by Colin.; every second Colin can choose to stay still at the current node or to move once along the edge connected to the current node, and arrive at the other node of this edge at the end of this second.Colin wants to chase Eva as soon as possible. Can you tell him what's the minimum time that Colin and Eva will be at the same node.q times, you need to tell Colin the minimum time for every game, and the corresponding index of the node.
Colin and Eva are playing a chasing game on a given tree with n n nodes, indexed from 1 1 to n n. Colin knows that Eva will start from node S S at time 0 , and move towards her destination node T T at the speed of 1 edge per second. (i.e. Assuming that the path from S S to T T is p_0, p_1, cdots, p_k,text{ } p_0 = S, p_k = T p ,p 1 ,⋯,p k , p =S,p k =T , then Eva will arrive at node p_i p i at time i i ) After arriving at node T T, Eva will stay still there until she is caught by Colin. Now Colin wants to chase Eva. At time 0, Colin is at node S' S ′ ; every second Colin can choose to stay still at the current node or to move once along the edge connected to the current node, and arrive at the other node of this edge at the end of this second. Colin wants to chase Eva as soon as possible. Can you tell him what's the minimum time that Colin and Eva will be at the same node. Colin and Eva will play this game q q times, you need to tell Colin the minimum time for every game, and the corresponding index of the node.
