思路：首先當然是要用樹的點分治了。根節點為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了。
comment(linker, "/STACK:1024000000,1024000000")<iostream><cstring><algorithm><cstdio><cmath><vector><map>
Maxn 100010
Maxm 200010
LL __int64
inf 0x7fffffff
<LL,LL> head[Maxn],vi[Maxn],e,ans,num,k,n,m,prime[ cnt[<Node>,-,,,]=( i=;i<=;i++=Exp[i-]*=ans=lans= add( u,=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++=v,edge[e].v=u,edge[e].next=head[v],head[v]=e++ dfssize( u,==(i=head[u];i!=-;i==(v!=fa&&!+=(size[v]>mx[u]) mx[u]= dfsroot( r, u,(size[r]-size[u]>mx[u]) mx[u]=size[r]-(mx[u]<mi) mi=mx[u],root=(i=head[u];i!=-;i==(v!=fa&&! dfsdis( u,Node d,=(j=;j<=k;j++)
+=(-(d.cnt[j]+node[root].cnt[j])%)%*+=hash[cc];
(i=head[u];i!=-;i==(v!=fa&&!(j=;j<=k;j++=(d.cnt[j]+node[v].cnt[j])% calc( i,j,ret==]=(i=head[u];i!=-;i==(!=
( r=;r<sz;r++)
=(j=;j<=k;j+++=q[r].cnt[j]*++ dfs(=+=
vi[root]=(i=head[root];i!=-;i==(!(scanf(,&n)!=,&(i=;i<=k;i++,&(i=;i<=n;i++,&,(j=;j<=k;j++(x%prime[j]==&&x!=++%=/=(x== cc=(j=;j<=k;j+++=(cc==++
(i=;i<n;i++,&u,&
