Greatest common divisors of the largest path on tree / Asking for help
Difference between en2 and en3, changed 2 character(s)
Hi guys, without further redo, let's get straight to the main problem!↵
↵
PROBLEM↵
==================↵
↵
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 existed somewhere in this Codeforces platform, if anyone know where is it, please give me the link. Thank you so much for your help.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Erisu._.3812 2022-08-18 19:10:25 2 Tiny change: 'o be exist somewhere' -> 'o be existed somewhere'
en2 English Erisu._.3812 2022-08-18 19:08:16 1 Tiny change: 'em!\n\nPROMBLEM\n====' -> 'em!\n\nPROBLEM\n===='
en1 English Erisu._.3812 2022-08-18 19:07:57 999 Initial revision (published)