### Erisu._.3812's blog

By Erisu._.3812, history, 6 weeks ago,

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 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 existed somewhere in this Codeforces platform, if anyone know where is it, please give me the link. Thank you so much for your help.

• +6

 » 6 weeks ago, # |   +1 Auto comment: topic has been updated by Erisu._.3812 (previous revision, new revision, compare).
 » 6 weeks ago, # |   +1 sorry if there were gramatically errors, I wrote this in hurry
 » 6 weeks ago, # |   +1 Auto comment: topic has been updated by Erisu._.3812 (previous revision, new revision, compare).
 » 6 weeks ago, # | ← Rev. 2 →   +1 interesting problem, im waiting for the solution ;-;
 » 6 weeks ago, # |   0 No
 » 6 weeks ago, # |   0 This most likely won't pass for N=2e5 in 0.5s, but you could do it with centroid decomposition and keeping track of the longest path you can get for each divisor of your current path's gcd for a weird $O(NlogN\sqrt[3]{N})$ solution.USACO has a guide on this trick.
•  » » 6 weeks ago, # ^ |   +11 You can do it without centroid decomposition in $O(N \cdot \max_{i \in \{1, \dots, N\}} P(i))$ where $P(\cdot)$ is the distinct prime divisor count function using a couple of global arrays. For a proof, for each prime $p \le N$, it contributes $O(1) + O(x_p)$ where $x_p$ is the number of elements divisible by $p$ in the array.
•  » » » 6 weeks ago, # ^ |   +8 Could you elaborate on the approach a bit please? I get the distinct primes part but how do you do it without CD?
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +11 You can trivially deal with paths of lengths 1. Define the value of an edge to be the gcd of the values of its endpoints. The gcd of nodes on a path is now equal to the gcd of values of edges on that path (this reduction is not really necessary but makes it easier to see why the complexity bound holds). For each distinct prime, consider the forest you get after adding edges with values divisible by that prime. Find the diameter for each component and take the maximum.
•  » » » » » 6 weeks ago, # ^ |   0 I think we shouldn't find the diameter for each component otherwise the time complexity would be $O(n\times \pi(n))=O(n^2/\log n)$ since we need $O(n)$ complexity for each prime numberTo avoid this we need some data structures to maintain the diameter of a connected component while adding edges so the complexity is actually $O(n\log n\times \max_{1\le i\le n} P(i))=O(n\log ^2n/\log\log n)$
•  » » » » » » 6 weeks ago, # ^ |   0 Oh I found that it's possible to maintain the diameter after adding an edge in $O(1)$ time with $O(n\log n)$ or $O(n)$ prework so that the complexcity is still $O(n\log n)$ :Dsorry for that :D
•  » » » » » » » 6 weeks ago, # ^ |   0 https://codeforces.com/contest/1101/problem/DFinally, I found the original problem on codeforce :>
•  » » » » » » » 6 weeks ago, # ^ |   +1 You can do something much easier like this. For every component, you can compute the diameter in $O(|V_\text{component}|)$.
 » 6 weeks ago, # |   +1 I guess you are talking about this problem: https://codeforces.com/problemset/problem/1101/D
•  » » 6 weeks ago, # ^ |   0 YES, Thank you for your help, but my time limit is just 0.5, but maybe O(nlogn) could pass