思路：首先当然是要用树的点分治了。根节点为root，那么经过root的合法路径数求出来这题就解决了。因为我们可以用分治枚举根，最后将所有根的路径数加起来就是结果。当然这里的根不是整棵树的根，是子树根。
我们为每个节点分配一个长度为30的数组记录给定因数在每个节点权值出现的次数。如果某几个权值相乘的值Value的三次根仍是整数的话，那么Value在给定因数的所有幂一定是3的倍数。通过这个转换，我们将所有的幂都对3取余，结果还是一样。
在判断经过root的合法路径数时，我们进入其一个子树，将经过的路径因数的幂相加，判读其是否有对立状态存在，若存在，结果+1。所谓对立状态就是能够合成合法路径的状态。
例如因数为 2,3,5.
那么 x节点的状态为 0,1,2 表示2的0次幂，3的1次幂，5的2次幂。
其对立状态就是 0,2,1。因为他这两条路径合成一条后，就变成了0,3,3.都是3的倍数。
状态数的记录，我们可以用long long 型的map。
要加栈，不然会RE。我就连续两次RE，加了就AC了。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#define Maxn 100010
#define Maxm 200010
#define LL __int64
#define inf 0x7fffffff
using namespace std;
map<LL,LL> hash;
int head[Maxn],vi[Maxn],e,ans,num,k,n,m,prime[],lans;
int mx[Maxn],mi,dis[Maxn],root,size[Maxn];
LL Exp[];
struct Node{
int cnt[];
}node[Maxn];
struct Edge{
int u,v,val,next;
}edge[Maxm];
vector <Node> q;
void init()
{
memset(vi,,sizeof(vi));
memset(head,-,sizeof(head));
memset(mx,,sizeof(mx));
memset(dis,,sizeof(dis));
q.clear();
hash.clear();
Exp[]=;
for(int i=;i<=;i++)
Exp[i]=Exp[i-]*;
e=ans=lans=;
}
void add(int u,int v)
{
edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++;
edge[e].u=v,edge[e].v=u,edge[e].next=head[v],head[v]=e++;
}
void dfssize(int u,int fa)
{
int i,v;
size[u]=;
mx[u]=;
for(i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(v!=fa&&!vi[v])
{
dfssize(v,u);
size[u]+=size[v];
if(size[v]>mx[u]) mx[u]=size[v];
}
}
}
void dfsroot(int r,int u,int fa)
{
int v,i;
if(size[r]-size[u]>mx[u]) mx[u]=size[r]-size[u];
if(mx[u]<mi) mi=mx[u],root=u;
for(i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(v!=fa&&!vi[v])
{
dfsroot(r,v,u);
}
}
}
void dfsdis(int u,Node d,int fa)
{
int i,v,j;
q.push_back(d);
LL cc=;
for(j=;j<=k;j++)//判断其是否存在对立状态
{
cc+=(-(d.cnt[j]+node[root].cnt[j])%)%*Exp[j];
}
lans+=hash[cc];//答案加上对立状态数
Node temp;
for(i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(v!=fa&&!vi[v])
{
for(j=;j<=k;j++)
{
temp.cnt[j]=(d.cnt[j]+node[v].cnt[j])%;
}
dfsdis(v,temp,u);
}
}
}
int calc(int u)
{
int i,j,ret=,sz,v;
lans=;
hash.clear();
hash[]=;
for(i=head[u];i!=-;i=edge[i].next)
{
q.clear();
v=edge[i].v;
if(!vi[v])
{
dfsdis(v,node[v],u);
sz=q.size();
//cout<<u<<" "<<v<<" "<<sz<<endl;
for(int r=;r<sz;r++)//回退时，记录这条子路径上的所有状态数。
{
LL cc=;
for(j=;j<=k;j++)
{
cc+=q[r].cnt[j]*Exp[j];
}
hash[cc]++;
}
}
}
return lans;
}
void dfs(int u)
{
int i,v,j;
mi=n;
dfssize(u,);
dfsroot(u,u,);
ans+=calc(root);
//cout<<root<<"************"<<endl;
vi[root]=;
for(i=head[root];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(!vi[v])
{
dfs(v);
}
}
}
int main()
{
int i,j,u,v;
LL x;
while(scanf("%d",&n)!=EOF)
{
init();
scanf("%d",&k);
for(i=;i<=k;i++)
scanf("%d",&prime[i]);
for(i=;i<=n;i++)
{
scanf("%I64d",&x);
memset(node[i].cnt,,sizeof(node[i].cnt));
for(j=;j<=k;j++)
{
while(x%prime[j]==&&x!=)
{
node[i].cnt[j]++;
node[i].cnt[j]%=;
x/=prime[j];
}
if(x==)
break;
}
int cc=;
for(j=;j<=k;j++)
cc+=node[i].cnt[j];
if(cc==)
ans++;
}
//printf("&&&&&&&&&&&&\n");
for(i=;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
}
dfs();
printf("%d\n",ans);
}
return ;
}