0
15

# problem

$$n\le 10^5,w\le 10^8$$

# code

/*
* @Author: wxyww
* @Date: 2020-02-05 16:57:50
*/
#include<map>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 100010;
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct node {
int v,nxt;ull w;
}e[N << 1];
void add(int u,int v,ull w) {
}
map<int,ull>ma;
ull Rand() {
return (ull)rand() * (ull)rand() * (ull)rand() * (ull)rand() * (ull)rand();
}
ull val[N];
int vis[N],pri[N],tot;
void pre() {
for(int i = 2;i <= 10000;++i) {
if(!vis[i]) {
pri[++tot] = i;
val[tot] = Rand();
}
for(int j = 1;j <= tot && i * pri[j] <= 10000;++j) {
vis[pri[j] * i] = 1;
if(i % pri[j] == 0) break;
}
}
}
ull get(int x) {
ull ret = 0;
for(int i = 1;i <= tot;++i) {
while(x % pri[i] == 0) {
x /= pri[i];
ret ^= val[i];
}
}
if(x != 1) {
if(!ma.count(x)) ma[x] = Rand();
ret ^= ma[x];
}
return ret;
}
ull dis[N];
ll anss;
map<ull,int>ans;
void dfs(int u,int fa) {
anss += ans[dis[u]] * 2;
ans[dis[u]]++;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;if(v == fa) continue;
dis[v] = dis[u] ^ e[i].w;
dfs(v,u);
}
}
int main() {
pre();