<p>There is a tree (i.e.,&nbsp;a connected, undirected graph that has no cycles) consisting of <code>n</code> nodes numbered from <code>0</code> to <code>n - 1</code> and exactly <code>n - 1</code> edges. Each node has a value associated with it, and the <strong>root</strong> of the tree is node <code>0</code>.</p>

<p>To represent this tree, you are given an integer array <code>nums</code> and a 2D array <code>edges</code>. Each <code>nums[i]</code> represents the <code>i<sup>th</sup></code> node&#39;s value, and each <code>edges[j] = [u<sub>j</sub>, v<sub>j</sub>]</code> represents an edge between nodes <code>u<sub>j</sub></code> and <code>v<sub>j</sub></code> in the tree.</p>

<p>Two values <code>x</code> and <code>y</code> are <strong>coprime</strong> if <code>gcd(x, y) == 1</code> where <code>gcd(x, y)</code> is the <strong>greatest common divisor</strong> of <code>x</code> and <code>y</code>.</p>

<p>An ancestor of a node <code>i</code> is any other node on the shortest path from node <code>i</code> to the <strong>root</strong>. A node is <strong>not </strong>considered an ancestor of itself.</p>

<p>Return <em>an array </em><code>ans</code><em> of size </em><code>n</code>, <em>where </em><code>ans[i]</code><em> is the closest ancestor to node </em><code>i</code><em> such that </em><code>nums[i]</code> <em>and </em><code>nums[ans[i]]</code> are <strong>coprime</strong>, or <code>-1</code><em> if there is no such ancestor</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2021/01/06/untitled-diagram.png" style="width: 191px; height: 281px;" /></strong></p>

<pre>
<strong>Input:</strong> nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
<strong>Output:</strong> [-1,0,0,1]
<strong>Explanation:</strong> In the above figure, each node&#39;s value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1&#39;s value is not coprime (gcd(3,3) == 3), but node 0&#39;s
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2021/01/06/untitled-diagram1.png" style="width: 441px; height: 291px;" /></p>

<pre>
<strong>Input:</strong> nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
<strong>Output:</strong> [-1,0,-1,0,0,0,-1]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>nums.length == n</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 50</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[j].length == 2</code></li>
	<li><code>0 &lt;= u<sub>j</sub>, v<sub>j</sub> &lt; n</code></li>
	<li><code>u<sub>j</sub> != v<sub>j</sub></code></li>
</ul>

class Solution:
    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
        # root at zero
        # tree, in edge form

        # nodes are not ancestors of themselves
        # return an array ans where
        #     ans[i] is the most recent ancestor value that is coprime to nums[i]

        # brute force: DFS + BT
        #     curr list has root to parent values
        #        can scan backwards in this list to find the most recent ancestor, if any, that is coprime
        #        for each node that's O(N) ancestors
        #        each gcd is log(v) time, so O(N*log(max)) time total per node
        #     N nodes total: O(N**2 log(max)) time
        #
        # that involves iterating over N values
        # but a number has at most log(value) distinct prime factors, and we can find those in O(log(value)) with some precomp
        # so we can record the most recent value with each prime factor
        # so suppose instead we take value v, <= max, and
        #     1. find distinct prime factors in O(log(max))
        #     2. find the most recent ancestor for each: O(log(max)) from a map
        #
        #        that will take O(log(max)) time per node, and O(N) nodes
        #
        # that's probably about as good as we'll get. Most recent (e.g. max index) over prior n values is
        # going to involve some extra wrangling

        # # 1. we need quick access to primes: Sieve of Eratosthenes time
        # M = sqrt(max(nums)) # x can have only one prime factor larger than M, so residue of trial div is a final prime
        #                     # and thus trial div above M is unnecessary
        # isPrime = [True]*(M+1)
        # primes = [2]
        # for x in range(3, M+1, 2):
        #     if not isPrime[x]: continue
            
        #     primes.append(x)
        #     for m in range(x*x, M+1, 2*x):
        #         # mults of m are composite
        #         # mults of m lower than x*x have the form y*x with y < x
        #         # we already marked off multiples of such y in earlier iterations
        #         isPrime[m] = False

        # # 2. quick trial division way to get primes
        # def iterPrimes(x: int) -> Iterator[int]:
        #     r = x
        #     for p in primes:
        #         if p*p > x: break

        #         if r % p == 0:
        #             yield p
        #             r //= p
        #             while r % p == 0: r //= p

        #         if r == 1: return

        #     if r > 1: yield r # x has only one prime factor above sqrt(x), and we divided out all lower factors

        # # 3. adjacency list to prepare for DFS from 0
        # N = len(nums)
        # adj = [[] for _ in range(N)]
        # for u, v in edges:
        #     adj[u].append(v)
        #     adj[v].append(u)

        # # oops: I just realized again we want coprime, so we'll iterate over primes that are not divisors of 
        # # 4. DFS + BT
        # ans = [-1]*


        # # ugh: want COPRIME, not those with a common factor, duh
        # # so sieve doesn't help us?
        
        # N = len(nums)
        # adj = [[] for _ in range(N)]
        # for u, v in edges:
        #     adj[u].append(v)
        #     adj[v].append(u)

        # ancestors = [] # indices of this node's ancestors
        # ans = [-1]*N
        # def dfs(u: int, p: int) -> None:
        #     for a in reversed(ancestors):
        #         if gcd(nums[a], nums[u]) == 1:
        #             ans[u] = a
        #             break
        #     # else: entry is already -1

        #     ancestors.append(u)
        #     for v in adj[u]:
        #         if v == p: continue
        #         dfs(v, u)

        #     ancestors.pop()

        # dfs(0, -1)
        # return ans

        ## above works, but n**2 log(max) for n ~ 1e5 is heinous

        # we need something faster

        # there are N ancestor values
        # we want nodes that have no common factors
        # current number x has prime factors p1..pk
        # we want ancestors that have none of these
        # so maybe we can iterate over all O(max/log(max)) prime factors, and find the max without that prime
        # THIS is what we need to do: max is just 50
        #
        # but how exactly?
        #  idea: record latest index of each number: push before descending, pop after
        #  iterate over prior indices of numbers comprime, O(max), and record max index among those numbers that are coprime
        #  O(N*max), acceptable
        
        indices = [[] for _ in range(max(nums)+1)] # x -> (h, a) with the height h and label a for all ancestors with value x
        adj = [[] for _ in range(len(nums))]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        ans = [-1]*len(nums)

        def dfs(u: int, h: int, p: int) -> None:
            best_h = -1
            best_a = -1
            for x in range(1, len(indices)): # ancestor values
                if indices[x] and best_h < indices[x][-1][0] and gcd(x, nums[u]) == 1:
                    best_h, best_a = indices[x][-1]

            ans[u] = best_a

            indices[nums[u]].append((h, u)) # u is an ancestor of its children, so append before we descend
            for v in adj[u]:
                if v == p: continue
                dfs(v, h+1, u)

            indices[nums[u]].pop()

        dfs(0, 0, -1)
        return ans
1748