Tom & Jerry
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Tom is trying to chase down Jerry. They're in a large house with n rooms. The rooms are connected by hallways. Furthermore, the rooms are designed in such a way that there is exactly one way to reach from one room to another room. Formally, the network of rooms in the house forms a Tree.
The rooms of the house are conveniently numbered from 1 through n. Initially, Tom and Jerry are in some rooms of the house. In each second, both Jerry and Tom make a move. Jerry moves first, followed by Tom. Note that both the movements of Jerry and Tom happen within a second. In a single move, a player might stay in the same room or can choose to move to some adjacent room. Both the players know each other's positions at all times. When both Tom and Jerry are in the same room, Tom will attack Jerry. Both the players play optimally, i.e. Jerry will try to avoid his death as long as he can, and Tom will try to catch him as soon as possible.
You are given Q queries. In each query, you are given two integers, x, y, where x denotes the room in which Tom is present, and y denotes the same for Jerry. You have to find the time at which Tom will catch Jerry.
The first line of the input contains an integer T denoting the number of the test cases.
The first line of each test case will contain two space separated integer n, Q denoting number of rooms in the house, and the number of queries, respectively.
Each of the next n - 1 lines contains two space separated integers u, v, denoting that there is an hallway between rooms u and v in the house.
Each of the next Q lines contains two space separated integers x, y, where x denotes the room in which Tom is present, whereas y denotes the room in which Jerry is present.
For each test case, output a single integer corresponding to time at which Tom will catch Jerry.
- 1 ≤ T ≤ 5
- 1 ≤ n, Q ≤ 105
- 1 ≤ u, v ≤ n
- 1 ≤ x, y ≤ n
Subtask #1: (10 points)
- 1 ≤ n, Q ≤ 100
Subtask #2: (15 points)
- In all the queries, Jerry's position is fixed i.e Jerry starts in the same room in all the queries..
Subtask #3: (15 points)
- In all the queries, Tom's position is fixed i.e Tom starts in the same room in all the queries.
Subtask #4: (15 points)
- 1 ≤ n ≤ 5000
Subtask #5: (45 points)
- Original Constraints
Input: 1 3 2 1 2 2 3 1 2 2 3 Output: 2 1
Example case 1. In first query, Tom is in room 1, whereas Jerry is in room 2. In first second, Jerry first moves from 2 to 3 followed by Tom moving from 1 to 2. In the next second, if Jerry moves from 3 to 2, Tom will stay at his position and attack Jerry. If Jerry decides to stay in room 3 itself, then Tom will move to room 3, and kill it. Overall, Tom is going to take 2 seconds to kill Jerry.
Example case 2. In the first second itself, Tom will kill Jerry, regardless whether Jerry decides to stay put or move from room 3 to 2.
|Tags||admin2 lca ltime42 medium-hard trees|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions