Description

一棵树,给每一条边一个权值 \(w_i\),求出所有满足权值之积为完全平方数的路径的条数

Sulotion

是完全平方数的充要条件是质因子出现次数为偶数,那么我们给每一个质因子一个随机一个权值,那么满足条件的路径就是异或和为 \(0\) 的路径

\(dsu\) 做一下就好了(别管我这个傻逼)

#include
    
     using namespace std;typedef long long ll;const int N=1e5+10,M=1e4+10;int n,prime[M],num=0,t[N];bool vis[M];int head[N],nxt[N*2],to[N*2],NUM=0;ll c[N*2],sed=41,LIM=1e15,ans=0,b[N];inline void link(int x,int y,ll z){    nxt[++NUM]=head[x];to[NUM]=y;head[x]=NUM;c[NUM]=z;    nxt[++NUM]=head[y];to[NUM]=x;head[y]=NUM;c[NUM]=z;}inline void priwork(){    for(int i=2;i
     
      A;inline ll seed(){return sed=(sed*41+99241)%LIM;}inline ll F(int x){    if(A.find(x)!=A.end())return A[x];    return A[x]=seed();}inline ll getval(int x){    ll ret=0;    for(int i=1;i<=num;i++){        if(x
      
       1)ret^=F(x);    return ret;}int sz[N],son[N];ll dis[N];inline void dfs1(int x){    sz[x]=1;    for(int i=head[x],u;i;i=nxt[i]){        if(sz[u=to[i]])continue;        dis[u]=dis[x]^c[i];dfs1(u);sz[x]+=sz[u];        if(sz[son[x]]