GCD Counting
You are given a tree consisting of $$$n$$$ vertices. A number is written on each vertex; the number on vertex $$$i$$$ is equal to $$$a_i$$$.Let's denote the function $$$g(x, y)$$$ as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex $$$x$$$ to vertex $$$y$$$ (including these two vertices). Also let's denote $$$dist(x, y)$$$ as the number of vertices on the simple path between vertices $$$x$$$ and $$$y$$$, including the endpoints. $$$dist(x, x) = 1$$$ for every vertex $$$x$$$.Your task is calculate the maximum value of $$$dist(x, y)$$$ among such pairs of vertices that $$$g(x, y) > 1$$$.
The first line contains one integer $$$n$$$ — the number of vertices $$$(1 \le n \le 2 \cdot 10^5)$$$.The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le 2 \cdot 10^5)$$$ — the numbers written on vertices.Then $$$n - 1$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ $$$(1 \le x, y \le n, x \ne y)$$$ denoting an edge connecting vertex $$$x$$$ with vertex $$$y$$$. It is guaranteed that these edges form a tree.
If there is no pair of vertices $$$x, y$$$ such that $$$g(x, y) > 1$$$, print $$$0$$$. Otherwise print the maximum value of $$$dist(x, y)$$$ among such pairs.
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

def bootstrap(f, stack=[]):

    def fun(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return fun

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
import math as mt
MAXN = 200001
spf = [0 for i in range(MAXN)]

def sieve():
    spf[1] = 1
    for i in range(2, MAXN):
        spf[i] = i
    for i in range(4, MAXN, 2):
        spf[i] = 2
    for i in range(3, mt.ceil(mt.sqrt(MAXN))):
        if spf[i] == i:
            for j in range(i * i, MAXN, i):
                if spf[j] == j:
                    spf[j] = i

def getFactorization(x):
    ret = list()
    while x != 1:
        ret.append(spf[x])
        x = x // spf[x]
    return list(set(ret))
sieve()

@bootstrap
def dfs(u, p):
    global ans
    req = defaultdict(lambda : [])
    for j in adj[u]:
        if j != p:
            curr = (yield dfs(j, u))
            for k in curr:
                req[k[0]].append(k[1])
    res = getFactorization(b[u])
    l = []
    for j in res:
        req[j].sort()
        l1 = len(req[j])
        if l1 == 0:
            l.append([j, 1])
            ans = max(ans, 1)
        if l1 >= 1:
            l.append([j, req[j][-1] + 1])
            ans = max(ans, l[-1][1])
        if l1 >= 2:
            ans = max(ans, req[j][-1] + req[j][-2] + 1)
    yield l
p = 10 ** 9 + 7
for _ in range(1):
    n = int(input())
    b = [0] + list(map(int, input().split()))
    adj = [[] for i in range(n + 1)]
    for j in range(n - 1):
        (u, v) = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    ans = 0
    dfs(1, 0)
    print(ans)
from collections import deque
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs(k, c):
    q = deque()
    q.append(k)
    color[k] = c
    while q:
        i = q.popleft()
        for j in G[i]:
            if color[j] ^ c and (not a[j - 1] % c):
                q.append(j)
                color[j] = c
    q = deque()
    q.append(i)
    dist[i] = 1
    while q:
        i = q.popleft()
        di = dist[i]
        for j in G[i]:
            if dist[j] == -1 and (not a[j - 1] % c):
                q.append(j)
                dist[j] = di + 1
    return di
n = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (x, y) = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
m = 200005
b = [[] for _ in range(m)]
for i in range(n):
    b[a[i]].append(i + 1)
color = [0] * (n + 1)
dist = [-1] * (n + 1)
p = [1] * m
ans = 0
for i in range(2, m):
    if not p[i]:
        continue
    for j in range(i, m, i):
        for k in b[j]:
            if color[k] ^ i:
                d0 = bfs(k, i)
                ans = max(ans, d0)
    for j in range(i, m, i):
        p[j] = 0
        for k in b[j]:
            dist[k] = -1
print(ans)
import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque, Counter, OrderedDict
import threading

def main():
    ans = 1
    flag = True
    primes = []
    for i in range(2, 500):
        v = 1
        for p in primes:
            if i % p == 0:
                v = 0
        if v:
            primes.append(i)
    n = int(input())
    a = [*map(int, input().split())]
    if sum(a) == n:
        flag = False
    for i in range(n):
        x = a[i]
        a[i] = []
        for p in primes:
            if x % p == 0:
                a[i].append([p, 1])
                x = x // p
                while x % p == 0:
                    x //= p
        if x != 1:
            a[i].append([x, 1])
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        (x, y) = map(int, input().split())
        adj[x - 1].append(y - 1)
        adj[y - 1].append(x - 1)
    leaves = []
    for i in range(n):
        if len(adj[i]) == 1:
            leaves.append(i)
    for i in range(n - 1):
        x = leaves.pop()
        y = adj[x][0]
        adj[y].remove(x)
        if len(adj[y]) == 1:
            leaves.append(y)
        for nx in a[x]:
            for ny in a[y]:
                if nx[0] == ny[0]:
                    ans = max([ans, nx[1] + ny[1]])
                    ny[1] = max([ny[1], nx[1] + 1])
    if not flag:
        print(0)
    else:
        print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    ''
    main()