题解 | #寻找小竹，python版本#

寻找小竹！

https://ac.nowcoder.com/acm/contest/45670/E

一、解题思路

如果 $x, y$ 路口是连通的，并且他们的优雅值存在至少两个共同的质因子，则共同优雅。

而题意是要我们求出最大的优雅连通块，因此很容易想到并查集。另外，求共同质因子，数据范围是 $5\times 10^6$ ，因此考虑线性筛+分解质因子

因此，考点并查集，分解质因子，线性筛

思路清晰了，代码实现也就比较简单了。

流程如下：

1.首先通过线性筛，把 $5 * 1 0^{6}$ 内的质数先筛选出来

2.然后把相邻的路口，并且共同优雅的路口，用并查集连通起来

3.输出最大的连通块即可

二、完整代码

import sys
import os
from io import BytesIO, IOBase

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


def I(): return input()


def II(): return int(input())


def MI(): return map(int, input().split())


def LI(): return list(input().split())


def LII(): return list(map(int, input().split()))


# import random
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from math import gcd
# import math
from bisect import bisect_left, bisect_right


n = II()
arr = [0] + LII()
pa = [i for i in range(n+1)]
size = [1]*(n+1)

def find(x):
    if pa[x] != x:
        pa[x] = find(pa[x])
    return pa[x]

# Python Version
def get_primes(MAXN):  #线性筛
    pri = []
    vis = [0]*(MAXN)
    cnt = 0
    for i in range(2, MAXN):
        if vis[i] == 0: # 如果没有被晒过
            pri.append(i) # 那么i就是质数
            cnt += 1 # 质数个数加1
        for j in range(0, cnt):
            x = i*pri[j]
            if x >= MAXN: break # 如果最小质因子得倍数已经超过了要求得限度,break‘
            vis[x] = 1
            if i%pri[j] == 0: # 表示之前被筛选过，break
                break
    return pri


pri = set(get_primes(5*10**5+1)) # 得到质数了

@lru_cache(None)
def fenjie(n):
    res = set()
    for i in pri:
        if i*i > n:
            break
        while n%i == 0:
            n //= i
            res.add(i)
    if n > 1: res.add(n)
    return res

def check(x, y):
    a = fenjie(x)
    b = fenjie(y)
    return len(a&b)

for _ in range(n-1):
    x, y = MI()
    if check(arr[x], arr[y])>=2: # 如果两个共同优雅
        a, b = find(x), find((y))
        if a == b: continue
        if size[a] > size[b]:
            size[a] += size[b]
            pa[b] = a
        else:
            size[b] += size[a]
            pa[a] = b

print(max(size))