Hi guys, without further redo, let's get straight to the main problem!
You're given an N nodes tree, which each of the node contains a weight ai, we call g(x, y) means GCD or greatest common divisors of all the nodes stay on the path from node x to node y, and d(x, y) is the distance between node x and node y. Your task is to find the longest path or the maximum d(x,y) which gives the g(x,y) strictly larger than 1 (>1).
N <= 2*1e5, a[i]<=N, d(x,x) = 1;
Definition for input: 1st line is N, 2nd line is N weights of N nodes, 3rd line + n-1 is the connection of node X to node Y
Example test case:
2 3 4
Time limit : 0.5s
Memory limit: 256 mb
little note: this problem is told to be existed somewhere in this Codeforces platform, if anyone know where is it, please give me the link. Thank you so much for your help.