题目分析：
蛮简单的一道题，对于每个数拆质因子，对于每个质因子找出最长链，在每个地方枚举一下拼接
代码：
#include<bits/stdc++.h>
using namespace std; const int maxn = ; int n,a[maxn],prime[maxn],flag[maxn],minn[maxn],num,ans;
vector <int> g[maxn];
vector <pair<int,int> > mp[maxn]; vector<int> cl[maxn]; void getprime(int N){
for(int i=;i<=N;i++){
if(!flag[i]){prime[++num] = i,minn[i] = i;}
for(int j=;j<=num&&i*prime[j]<=N;j++){
flag[i*prime[j]] = ;
minn[i*prime[j]] = prime[j];
if(i%prime[j] == ) break;
}
}
} void read(){
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<n;i++){
int u,v; scanf("%d%d",&u,&v);
g[u].push_back(v); g[v].push_back(u);
}
} void dp(int now,int fa){
for(int i=;i<g[now].size();i++){
if(g[now][i] == fa) continue;
dp(g[now][i],now);
}
int p = a[now];
while(p != ){cl[minn[p]].clear(); p /= minn[p]; }
for(int i=;i<g[now].size();i++){
if(g[now][i] == fa) continue;
for(int j=;j<mp[g[now][i]].size();j++){
if(a[now] % mp[g[now][i]][j].first == ){
cl[mp[g[now][i]][j].first].push_back(mp[g[now][i]][j].second);
}
}
}
p = a[now];
while(p != ){
int z = minn[p]; while(p%z == ) p /= z;
int maxx = ,sec = ;
for(int i=;i<cl[z].size();i++){
if(cl[z][i] >= maxx) sec = maxx,maxx = cl[z][i];
else if(cl[z][i] > sec) sec = cl[z][i];
}
mp[now].push_back(make_pair(z,maxx+));
ans = max(ans,maxx+sec+);
}
} void work(){
getprime();
dp(,);
printf("%d\n",ans);
} int main(){
read();
work();
return ;
}