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, Swift-4.1, 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

?