Hi guys, without further redo, let's get straight to the main problem!↵
↵
PROMBLEM↵
==================↵
↵
You're given an N nodes tree, which each of the node contains a weight a[i] (i<=N), 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:↵
↵
Input: ↵
↵
3↵
↵
2 3 4↵
↵
1 3↵
↵
2 3↵
↵
Output: ↵
↵
2↵
↵
Time limit : 0.5s↵
↵
Memory limit: 256 mb↵
↵
little note: this problem is told to be exist somewhere in this Codeforces platform, if anyone know where is it, please give me the link. Thank you so much for your help.↵
↵
PRO
==================↵
↵
You're given an N nodes tree, which each of the node contains a weight a[i] (i<=N), 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:↵
↵
Input: ↵
↵
3↵
↵
2 3 4↵
↵
1 3↵
↵
2 3↵
↵
Output: ↵
↵
2↵
↵
Time limit : 0.5s↵
↵
Memory limit: 256 mb↵
↵
little note: this problem is told to be exist somewhere in this Codeforces platform, if anyone know where is it, please give me the link. Thank you so much for your help.↵