Overlapping Path Hackerearth

general
, , ,
1

Please Note: This is not an on-going Challenge question

Question :

There are N cities in the Byteland which are connected by N-1 bidirectional roads. Given two cities of the Byteland u and v. Now, you have to find the tow cities x and y of the Byteland such that the path between these tow cities overlaps the path between the given cities u and v completely and the gcd(x,y) is maximum possible.

Note: It is guaranteed that the graph is connected.

Input Format

The first line of the input contains an integer T, the total number of test cases.

Then T test cases follow, the first line of each test case contains an integer N, the total number of cities in the Byteland.

Then N-1 lines follow, the first line of each test case contains two separated integers a and b representing that there is a bidirectional road between the city a and b.

The next line contains two space-separated integers u and v.

Output Format

In the single line of the output print an integer representing the maximum possible gcd of the cities x and y.

Constraints

1 \leq T \leq 10

1 \leq N \leq 5 \times 10^{5}

1 \leq a,b,u,v \leq N

Sample Input

$2 \
6 \
1 , , , , 2 \
1 , , , , 3 \
2 , , , , 4 \
2 , , , , 5 \
2 , , , , 6 \
1 , , , , 3 \
10 \
1 , , , , 4 \
1 , , , , 5 \
1 , , , , 2 \
4 , , , , 3 \
4 , , , , 6 \
5 , , , , 7 \
2 , , , , 10 \
2 , , , , 9 \
2 , , , , 8 \
4 , , , , 2 \$

Sample Output

3 \\ 4

Explaination :

Sample test case 2:

The path from u to v is 4 \rightarrow 1 \rightarrow 2

Now, some of the paths which are completely overlaps the path from u to v are:

4 \rightarrow 1 \rightarrow 2 \rightarrow 10 \\ 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 9 \\ 4 \rightarrow 1 \rightarrow 2 \rightarrow 8

and so on…

Note that, selecting the path from 4 to 8 completely overlaps the path u and v, and also the gcd(4,8) = 4 which is the maximum possible.

Time Limit: 3.0 sec(s) for each input file

I have thought of finding all paths between every two pair of vertices and store them. Then find whether u and v is contained in them. For all paths which satisfies the previous conditions, I will find gcd of the end points of the path. But this seems too complex. I guess it could be solved in other simple way. But I couldn’t think of any other way. Can anyone suggest what to do. I could post my code link if it is needed. Thanks.

2

I think the following approach should work->

We can find path from u to v using DFS and store all the vertices in an array

Now the problem reduces to finding two distinct elements from the array with max gcd.

This can be done in nlogn time.

3

I guess this didn’t work. May be I have missed something from my side. I have found path from u to v using DFS and store the vertices in the array. For the second case I got array of dfs as [4, 1, 5, 7, 2, 3, 6], and the maximum gcd here is 3, but the answer is 4. Please see the code if needed. OvelappingPath.java - Pastebin.com

4

Provide the question link…I do not understand Java much

5

I am sorry that the question was asked in a past hiring challenge and unfortunately they have not provided the practice link after the contest has ended. As you may know they do not provide practice links of questions of every hiring challenge. But be assured this question is word to word correct.

6

Ohh…I miss understood the question…The approach i gave is wrong…Sorry :frowning:

7

Kindly help anyone? There must be a better approach to solve it.