大家都知道 $\varphi(n)=n\prod_{p|n}\frac {p-1} p$吧。

以及，$\sum_{d^2|n}\mu(\frac n {d^2})$ 实际上是刘维尔函数。刘维尔函数就是 $\lambda(n)=(-1)^{\Omega(n)}$，其中 $\Omega(n)$ 是 $n$ 的质因子个数（可重）。

可以知道 $\lambda$ 是 完全积性 的。

于是原柿就可以这样化简：

$$\prod_{i=1}^n\prod_{j=i+1}^ndis(i,j) \times \lambda(dis(i,j))\prod_{p|dis(i,j)}\frac {p-1} p $$

前半部分计算每一个 $a$ 对答案的贡献，我们来讨论后半部分。

$$\prod_{i=1}^n\prod_{j=i+1}^n\prod_{p|dis(i,j)}\frac {p-1} p $$$$\prod_p\prod_{i=1}^n\prod_{j=i+1}^n(\frac {p-1} p)^{[p|dis(i,j)]} $$$$\prod_p(\frac {p-1} p)^{\sum_{i=1}^n\sum_{j=i+1}^n[p|dis(i,j)]} $$

于是我们可以枚举 $p$，然后统计有多少条路径中有 $p$，复杂度 $O(n^2V)$。

再想想，我们可以使用树形 DP 来统计这东西，复杂度 $O(nV)$。

但实际上出现的质数最有 $O(5n)$，所以实际上复杂度是 $O(5n^2)$ 的。

我们在树上标记 $p|a_u$ 的所有节点 $u$，容易发现这些节点将树分成了若干个连通块（被标记的节点单独算一个连通块），两两之间都会对答案产生贡献。

假设有 $cnt$ 个连通块，连通块的大小分别为 $B_1,B_2,...B_{cnt}$。

那么路径条数就是：

$$\sum_{i=1}^{cnt}\sum_{j=i+1}^{cnt}B_i \times B_j$$

稍微转化一下可以得到答案是：

$$\frac {(\sum_{i=1}^{cnt}B_i)^2-\sum_{i=1}^{cnt}B_i^2} 2 $$

也就是

$$\frac {n^2-\sum_{i=1}^{cnt}B_i^2} 2$$

只需要找到每个连通块大小的平方即可。

继续优化，发现可以使用树形 $\rm DP$ 来优化这玩意儿，于是就只需要树上被标记过的节点，可以使用虚树优化。在分解质因子的时候优化一下，复杂度 $O(V+7n\log n)$。

不过其实可以省掉虚树的排序，在 DFS 时分解质因子即可。

std:

#include<cstdio>
#include<vector>
typedef unsigned uint;
typedef unsigned long long ull;
const uint M=1e5+5,V=1e6+5,mod=998244353,MOD=998244352;
uint n,mx,ans=1,a[M];std::vector<uint>id[78499],G[M];
uint dfc,f[M],d[M],son[M],siz[M],top[M];ull s2[M];
uint fs[M],fa[M],siz1[M];ull siz2[M];bool vis[M];
uint tp,tot,q[M],stk[M];uint Tp,del[M];
uint Top,pri[78499],pos[V];
inline uint pow(uint a,uint b){
	uint ans=1;
	for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;
	return ans;
}
inline void sieve(const uint&n){
	register uint i,j,x;
	for(i=2;i<=n;++i){
		if(!pos[i])pri[++Top]=i,pos[i]=Top;
		for(j=1;j<=Top&&(x=i*pri[j])<=n;++j)if((pos[x]=pos[i])==j)break;
	}
}
void DFS1(const uint&u){
	uint x=a[u],y;bool tag=false;siz[u]=1;d[u]=d[f[u]]+1;
	while(x^1){
		id[pos[x]].push_back(u);y=pri[pos[x]];
		while(!(x%y))x=1.*x/y,tag=!tag;
	}
	for(uint&v:G[u]){
		if(v==f[u])continue;
		f[v]=u;DFS1(v);siz[u]+=siz[v];s2[u]+=1ull*siz[v]*siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
	ans=1ull*ans*pow(tag?mod-a[u]:a[u],(1ull*n*n-s2[u]-1ull*(n-siz[u])*(n-siz[u])-1>>1)%MOD)%mod;
}
void DFS2(const uint&u,const uint&tp){
	top[u]=tp;
	if(!son[u])return;DFS2(son[u],tp);
	for(uint&v:G[u]){
		if(v==f[u]||v==son[u])continue;
		DFS2(v,v);
	}
}
inline uint LCA(uint u,uint v){
	while(top[u]^top[v]){
		if(d[top[u]]>d[top[v]])u=f[top[u]];
		else v=f[top[v]];
	}
	return d[u]>d[v]?v:u;
}
inline uint Find(uint u,uint v){
	while(top[u]^top[v]){
		if(f[top[u]]==v)return top[u];
		u=f[top[u]];
	}
	return son[v];
}
inline void Insert(const uint&u){
	if(!tp)return void(stk[tp=1]=u);
	uint v=LCA(u,stk[tp]);
	while(tp>1&&d[v]<d[stk[tp-1]])G[stk[tp-1]].push_back(stk[tp]),--tp;
	if(d[v]<d[stk[tp]])G[v].push_back(stk[tp--]);
	if(!tp||stk[tp]!=v)stk[++tp]=v;
	if(stk[tp]!=u)stk[++tp]=u;
}
inline void Build(){
	tp=0;if(q[1]!=1)stk[tp=1]=1;
	for(register uint i=1;i<=tot;++i)Insert(q[i]),vis[q[i]]=true;
	while(tp>1)G[stk[tp-1]].push_back(stk[tp]),--tp;
}
ull Query(const uint&u){
	ull S=0,ans=0;
	for(uint&v:G[u]){
		fs[v]=Find(v,u);fa[v]=u;ans+=Query(v);S+=1ull*siz[fs[v]]*siz[fs[v]];
		if(vis[u]&&vis[v])ans+=1ull*(siz[fs[v]]-siz[v])*(siz[fs[v]]-siz[v]);
		if(vis[v]){
			siz1[u]+=siz[fs[v]];siz2[u]+=1ull*siz[fs[v]]*siz[fs[v]];
		}
		else{
			siz1[u]+=siz1[v];siz2[u]+=siz2[v];
		}
	}
	if(!vis[u]){
		if(vis[fa[u]])ans+=1ull*(siz[fs[u]]-siz1[u])*(siz[fs[u]]-siz1[u]);
		if(!fa[u])ans+=1ull*(n-siz1[u])*(n-siz1[u]);
	}
	else ans+=s2[u]-S+1;
	del[++Tp]=u;
	return ans;
}
signed main(){
	register uint i,u,v;ull n2;
	scanf("%d",&n);n2=1ull*n*n;
	for(i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);G[v].push_back(u);
	}
	for(i=1;i<=n;++i)scanf("%u",a+i),mx=a[i]>mx?a[i]:mx;sieve(mx);
	DFS1(1);DFS2(1,1);
	for(i=1;i<=n;++i)G[i].clear();
	for(i=1;i<=Top;++i){
		if(id[i].empty())continue;
		for(uint&u:id[i])q[++tot]=u;Build();tot=0;
		ans=1ull*ans*pow(1ull*(pri[i]-1)*pow(pri[i],mod-2)%mod,(n2-Query(1)>>1)%MOD)%mod;
		while(Tp){
			fs[del[Tp]]=fa[del[Tp]]=siz1[del[Tp]]=siz2[del[Tp]]=0;
			G[del[Tp]].clear();vis[del[Tp]]=false;
			--Tp;
		}
	}
	printf("%u",ans);
}