链接：https://ac.nowcoder.com/acm/contest/45670/E
来源：牛客网
题目大意：
有n个城市，n-1条道路，每个城市都有它自己的优雅值ai
而如果两个相邻的路口的优雅值存在至少两个共同的质因子，那么就说这两个相邻的路口就是共同优雅的。
共同优雅联通块定义为：在城市中选取若干个路口，若这些路口们两两互相联通，且每两个相邻的路口都是共同优雅的，则该联通块称为共同优雅联通块。
问我们最大的共同优雅联通块里面包含了多少座城市？
输入
4
12 12 4 18
1 2
1 3
2 4
输出
3
说明
最大优雅联通块为 1,2,4三个路口所在的联通块,两两相邻的路口均包含 2,3 两个质因子。
有思路但是实现不好，唔，加练！
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL INF=1e9;
const LL N=5000200,M=2002;
LL primes[N],cnt=0;
bool st[N];
LL n,ans=0,a[N],sum[N];
//sum[i]记录当前节点i所包含的满足城市的数量
vector<LL> g[N];
//线性筛板子
void get_primes(LL n)
{
for(LL i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++]=i;
for(LL j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
void dfs(LL u,LL fa)
{
//每次遍历到一个点的时候，最少它就只有它自己一个点符合条件
sum[u]=1;
for(LL i=0;i<g[u].size();i++)
{
LL idx=g[u][i];
if(idx==fa) continue;
dfs(idx,u);
//找到当前节点和父节点的共同最大公约数
//这样就可以直接在gcd这个数字上寻找相同的质数因子
LL gd=__gcd(a[u],a[idx]);
LL num=0;
for(LL i=0;i<cnt;i++)//在我们已经标记过的质因子上比对一下
{
if(gd==1) break;
if(!st[gd])//这个质数存在，因为这就是个质数了，不可再分
{
num++;
break;
}
if(gd%primes[i]==0)
{
num++;
if(num>=2) break;
while(gd%primes[i]==0)//约去相同质因子
{
gd/=primes[i];
}
}
}
if(num>=2) sum[u]+=sum[idx];//达标:当前节点记录往下的子节点
}
ans=max(ans,sum[u]);
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
//cin>>T;
get_primes(5e6);//先获取数据范围内的所有质数
while(T--)
{
cin>>n;
for(LL i=1;i<=n;i++)
cin>>a[i];
for(LL i=1;i<n;i++)
{
LL x,y;
cin>>x>>y;//建边
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,-1);//从根节点跑一跑
cout<<ans<<endl;
}
return 0;
}