比较简单的套路题，刚开始把点权看成边权然后想了个并查集维护直径的方法
后来发现是点权，但是显然可以化成边权于是就直接做了……（丝毫没有意识到直接BFS求直径更快）
首先显然我们要枚举一个质因子，把它所有倍数的边给找出来，然后只考虑选择这些点，求联通块的最大直径
因为每个数的质因数是$log$级别的，因此这部分是$O(nlog n)$，接下来就是常用的技巧
记录一个联通块内的直径两端点，每次合并两个联通块时直接套路$6$种情况即可，用并查集维护
注意这样的话树上距离就要写$O(1)$求LCA，不然就卡成$O(nlog^ 2n)$了
总复杂度$O(nlog n imes alpha (n))$
#pragma GCC optimize(2)
#include<cstdio>
#include<utility>
#include<vector>
#include<map>
#include<iostream>
#define RI register int
#define CI const int&
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
typedef vector <pi>:: iterator VPI;
const int N=100005;
struct edge
{
int to,nxt;
}e[N<<1]; vector <pi> ev[N*20]; map <int,int> trs; int fa[N],u[N],v[N];
int n,head[N],cnt,x,y,a[N],prime[N],tot,id,stk[N],top,ans; bool vis[N],ext[N];
inline int gcd(CI x,CI y)
{
return y?gcd(y,x%y):x;
}
inline int getid(CI x)
{
if (trs.count(x)) return trs[x]; else return trs[x]=++id;
}
#define P(x) prime[x]
inline void init(CI n=32000)
{
vis[1]=1; for (RI i=2,j;i<=n;++i)
{
if (!vis[i]) P(++tot)=i;
for (j=1;j<=tot&&i*P(j)<=n;++j)
if (vis[i*P(j)]=1,i%P(j)==0) break;
}
}
inline void resolve(int v,CI x,CI y)
{
for (RI i=1;i<=tot&&P(i)*P(i)<=v;++i) if (v%P(i)==0)
{
ev[getid(P(i))].pb(mp(x,y)); while (v%P(i)==0) v/=P(i);
}
if (v!=1) ev[getid(v)].pb(mp(x,y));
}
#undef P
inline void addedge(CI x,CI y)
{
e[++cnt]=(edge){y,head[x]}; head[x]=cnt;
e[++cnt]=(edge){x,head[y]}; head[y]=cnt;
}
#define to e[i].to
inline void DFS(CI now=1,CI fa=0)
{
for (RI i=head[now];i;i=e[i].nxt) if (to!=fa)
resolve(gcd(a[now],a[to]),now,to),DFS(to,now);
}
class Tree_Distance_Solver
{
private:
int f[N<<1][20],dep[N],idx,dfn[N],log[N<<1];
inline int mindep(CI x,CI y)
{
return dep[x]<dep[y]?x:y;
}
inline int getLCA(int x,int y)
{
if (!x||!y) return 0; x=dfn[x]; y=dfn[y]; if (x>y) swap(x,y);
int k=log[y-x+1]; return mindep(f[x][k],f[y-(1<<k)+1][k]);
}
public:
inline void DFS(CI now=1,CI fa=0)
{
dep[now]=dep[fa]+1; f[++idx][0]=now; dfn[now]=idx;
for (RI i=head[now];i;i=e[i].nxt) if (to!=fa) DFS(to,now),f[++idx][0]=now;
}
inline void init(void)
{
RI i,j; for (log[0]=-1,i=1;i<=idx;++i) log[i]=log[i>>1]+1;
for (j=1;j<20;++j) for (i=1;i+(1<<j)-1<=idx;++i)
f[i][j]=mindep(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
inline int getdis(CI x,CI y)
{
return dep[x]+dep[y]-(dep[getLCA(x,y)]<<1);
}
}T;
#undef to
inline int getfa(CI x)
{
return x!=fa[x]?fa[x]=getfa(fa[x]):x;
}
inline void Union(int x,int y)
{
x=getfa(x); y=getfa(y); fa[y]=x;
int d1=T.getdis(u[x],v[x]),d2=T.getdis(u[y],v[y]),
d3=T.getdis(u[x],u[y]),d4=T.getdis(u[x],v[y]),
d5=T.getdis(v[x],u[y]),d6=T.getdis(v[x],v[y]),
md=max(d1,max(d2,max(d3,max(d4,max(d5,d6)))));
if (d2==md) u[x]=u[y],v[x]=v[y]; else if (d3==md) v[x]=u[y]; else if (d4==md) v[x]=v[y];
else if (d5==md) u[x]=v[x],v[x]=u[y]; else if (d6==md) u[x]=v[x],v[x]=v[y];
}
inline int getdiam(int x)
{
x=getfa(x); return T.getdis(u[x],v[x]);
}
int main()
{
//freopen("tree.in","r",stdin); freopen("tree_.out","w",stdout);
RI i; for (init(),scanf("%d",&n),i=1;i<n;++i) scanf("%d%d",&x,&y),addedge(x,y);
for (i=1;i<=n;++i) scanf("%d",&a[i]); for (i=1;i<=n;++i) fa[i]=u[i]=v[i]=i;
for (DFS(),T.DFS(),T.init(),i=1;i<=id;++i)
{
int ret=0; for (VPI it=ev[i].begin();it!=ev[i].end();++it)
{
Union(it->fi,it->se); ret=max(ret,getdiam(it->fi));
if (!ext[it->fi]) stk[++top]=it->fi,ext[it->fi]=1;
if (!ext[it->se]) stk[++top]=it->se,ext[it->se]=1;
}
ans=max(ans,ret); while (top) fa[stk[top]]=u[stk[top]]=v[stk[top]]=stk[top],ext[stk[top--]]=0;
}
return printf("%d",ans+1),0;
}