C++ :

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define gc (c=getchar())
#define pb push_back
int read()
{
	char c;
	while(gc<'0');
	int x=c-'0';
	while(gc>='0')x=x*10+c-'0';
	return x;
}

template <class T> void chmax(T &x,const T &y)
{
	if(x<y)x=y;
}

const int N=1e5+5,U=4e4;
int a[N],ans;
map<int,int>dp[N];
int pr[U],pcnt;bool mark[U+5];
vector<int>lk[N];

void init()
{
	for(int i=2;i<=U;++i)
	{
		if(!mark[i])pr[++pcnt]=i;
		for(int j=1,x;i*(x=pr[j])<=U;++j)
		{
			mark[i*x]=1;
			if(i%x==0)break;
		}
	}
}

int st[20],ndp[20],top;
void fen(int now)
{
	top=0;
	for(int i=1,x;x=pr[i],x*x<=now;++i)
	if(now%x==0)
	{
		st[++top]=x;
		while(now/=x,now%x==0);
	}
	if(now>1)st[++top]=now;
	memset(ndp+1,0,top*sizeof(int));
}
void dfs(int x,int fr)
{
	for(vector<int>::iterator it=lk[x].begin();it!=lk[x].end();++it)
	{
		int y=*it;
		if(y==fr)continue;
		dfs(y,x);
	}
	fen(a[x]);
	for(vector<int>::iterator it=lk[x].begin();it!=lk[x].end();++it)
	{
		int y=*it;
		if(y==fr)continue;
		for(int h=1;h<=top;++h)
		{
			int k=st[h];
			if(!dp[y].count(k))continue;
			chmax(ans,ndp[h]+dp[y][k]+1);
			chmax(ndp[h],dp[y][k]);
		}
	}
	for(int h=1;h<=top;++h)
	{	
			int k=st[h];
			dp[x][k]=ndp[h]+1;
	}
}

int main()
{
	//freopen("1.in","r",stdin);
	int n;cin>>n;
	rep(i,1,n-1)
	{
		int x=read(),y=read();
		lk[x].pb(y);lk[y].pb(x);
	}
	rep(i,1,n)a[i]=read();
	init();
	dfs(1,0);
	cout<<ans;
}