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.