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.
Auto comment: topic has been updated by Erisu._.3812 (previous revision, new revision, compare).
sorry if there were gramatically errors, I wrote this in hurry
Auto comment: topic has been updated by Erisu._.3812 (previous revision, new revision, compare).
interesting problem, im waiting for the solution ;-;
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.
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.
Could you elaborate on the approach a bit please? I get the distinct primes part but how do you do it without CD?
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.
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 number
To 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)$$$
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)$$$ :D
sorry for that :D
You can do something much easier like this. For every component, you can compute the diameter in $$$O(|V_\text{component}|)$$$.
I guess you are talking about this problem: https://codeforces.com/problemset/problem/1101/D