Erisu._.3812's blog

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

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.

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by Erisu._.3812 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

sorry if there were gramatically errors, I wrote this in hurry

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by Erisu._.3812 (previous revision, new revision, compare).

»
6 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

interesting problem, im waiting for the solution ;-;

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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   Vote: I like it +11 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)$$$

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I guess you are talking about this problem: https://codeforces.com/problemset/problem/1101/D

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    YES, Thank you for your help, but my time limit is just 0.5, but maybe O(nlogn) could pass