Greatest common divisors of the largest path on tree / Asking for help

Revision en1, by Erisu._.3812, 2022-08-18 19:07:57

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 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:

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.

Tags tree, lca/rmq, longest path, need 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)