### The-Winner's blog

By The-Winner, 4 months ago,

I was wondering if there is any faster algorithm than O(N^2) that solves the following problem: Given a tree made of N nodes, where each node has an integer value asociated to it, find the minimum/maximum distance between two nodes whose values are coprime(if such a pair exists).

For example, given the following tree:

The minimum distance is 1 and can be obtained in multiple ways, but one of them is:

And the maximum distance is 4 and can be obtained like this:

I couldn't find anything like this by googling so I thought this is the best place to ask. Thank you in advance.

• +41

 » 4 months ago, # |   -9 What's the constraint for ai
•  » » 4 months ago, # ^ |   -7 I didn't find this problem anywhere, just thought about it, I suppose you can make it <=N or <=1e6 or 1e7.
 » 4 months ago, # | ← Rev. 2 →   0 Deleted.
 » 4 months ago, # | ← Rev. 3 →   0 It can be solved using centroid decomposition but I'm not aware of the details
•  » » 4 months ago, # ^ |   0 why are you so sure that it can be solved with it?
•  » » 4 months ago, # ^ |   0 How to use it here?
 » 4 months ago, # |   +21 By using centroid decomposition you can turn the problem into finding $b_i = \max_{i\perp j} a_j$, which can be solved by using parallel binary search in $O(n \log n 2^{\omega(n)})$.The whole complexity is $O(n \log^2 n 2^{\omega(n)})$.
•  » » 4 months ago, # ^ |   +5 How are you using parallel binary search if there are no queries ?
•  » » » 4 months ago, # ^ |   +5 Each $b_i$ is a query.