思路：首先当然是要用树的点分治了。根节点为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[31],lans; int mx[Maxn],mi,dis[Maxn],root,size[Maxn]; LL Exp[31]; struct Node{ int cnt[31]; }node[Maxn]; struct Edge{ int u,v,val,next; }edge[Maxm]; vector <Node> q; void init() { memset(vi,0,sizeof(vi)); memset(head,-1,sizeof(head)); memset(mx,0,sizeof(mx)); memset(dis,0,sizeof(dis)); q.clear(); hash.clear(); Exp[0]=1; for(int i=1;i<=30;i++) Exp[i]=Exp[i-1]*3; e=ans=lans=0; } 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]=1; mx[u]=0; for(i=head[u];i!=-1;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!=-1;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=0; for(j=1;j<=k;j++)//判断其是否存在对立状态 { cc+=(3-(d.cnt[j]+node[root].cnt[j])%3)%3*Exp[j]; } lans+=hash[cc];//答案加上对立状态数 Node temp; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(v!=fa&&!vi[v]) { for(j=1;j<=k;j++) { temp.cnt[j]=(d.cnt[j]+node[v].cnt[j])%3; } dfsdis(v,temp,u); } } } int calc(int u) { int i,j,ret=0,sz,v; lans=0; hash.clear(); hash[0]=1; for(i=head[u];i!=-1;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=0;r<sz;r++)//回退时，记录这条子路径上的所有状态数。 { LL cc=0; for(j=1;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,0); dfsroot(u,u,0); ans+=calc(root); //cout<<root<<"************"<<endl; vi[root]=1; for(i=head[root];i!=-1;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=1;i<=k;i++) scanf("%d",&prime[i]); for(i=1;i<=n;i++) { scanf("%I64d",&x); memset(node[i].cnt,0,sizeof(node[i].cnt)); for(j=1;j<=k;j++) { while(x%prime[j]==0&&x!=0) { node[i].cnt[j]++; node[i].cnt[j]%=3; x/=prime[j]; } if(x==0) break; } int cc=0; for(j=1;j<=k;j++) cc+=node[i].cnt[j]; if(cc==0) ans++; } //printf("&&&&&&&&&&&& "); for(i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); } dfs(1); printf("%d ",ans); } return 0; }