All Tracks Problem

Maximum Safety
Tag(s):

Medium-Hard

Problem
Editorial
Analytics

Kevin wants to hide from Marv in the city. The city consists of $$N$$ junctions connected with roads. There are $$N-1$$ roads, each of length $$1$$. So the city is a tree. Root of this tree is junction $$1$$.

For each of the next $$M$$ days Kevin wants to hide in one of the junctions. Kevin knows that Marv is located in junction $$a_i$$ on the $$i$$-th day. Kevin also believes that junction $$v$$ is safe only if $$v$$ is in the subtree of vertex $$b_i$$. The safety of vertex $$v$$ is equal to the distance between $$v$$ and $$a_i$$. Help Kevin to find the maximum safety possible for each day.

Input format:

The first line of input will contain an integer $$T$$, denoting the number of test cases.
Each test case starts with 2 numbers $$N$$ and $$M$$. Next $$N-1$$ lines contains 2 numbers $$u_i$$ and $$v_i$$ - junctions connected by a road. Next $$M$$ lines contains 2 numbers $$a_i'$$ and $$b_i'$$. To find actual values of $$a_i$$ and $$b_i$$ Kevin does the following steps:

  • let $$d_{i-1}$$ be the answer on $$i-1$$-th day.
  • $$a_i = ((a_i' - 1 + d_{i-1})\space mod \space N) + 1$$
  • $$b_i = ((b_i' - 1 + d_{i-1})\space mod \space N) + 1$$
  • assume that $$d_0=0$$

Output format:

For every test case output $$M$$ numbers - maximum safety for each day.

Constraints:

  • $$1 \le T \le 10$$
  • (20 points): $$1 \le N \le 1000, 1 \le M \le 1000$$
  • (30 points): $$1 \le N \le 10^5, 1 \le M \le 10^5$$ , $$a_i$$ is not in the subtree of $$b_i$$.
  • (50 points): $$1 \le N \le 10^5, 1 \le M \le 10^5$$.
SAMPLE INPUT
1
7 4
1 2
1 3
1 4
4 5
4 6
5 7
2 4
1 7
1 1
4 1
SAMPLE OUTPUT
4
2
0
2
Explanation

Actual values of $$a_i$$ and $$b_i$$:
Day 1 : $$a_1 = 2 , b_1 = 4$$
Day 2 : $$a_2 = 5 , b_1 = 4$$
Day 3 : $$a_1 = 3 , b_1 = 3$$
Day 4 : $$a_1 = 4 , b_1 = 1$$

Tree from the sample case:

sample

On the first day junction 7 has the maximum safety and its distance from junction 2 is 4. On the second day junction 6 has the maximum safety and its distance from junction 5 is 2. Note that distance to junction 2 is 3 but junction 2 is not safe as it is not in the subtree of juntion 4.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications