和成爷达成一致，被卡随机的话就是过了

考虑一个完全平方数的所有质因子次幂一定是偶数，于是对于每一条边我们都只保留其出现次数为奇数的质因子

注意到有一个点的\(w\leq 80\)，于是考虑状压质因子，对于第\(i\)个质数，我们定义其权值为\(2^{i-1}\)，这样我们就把每一条边的权值都变成了一个二进制数，现在只需要求有多少条路径的异或和为\(0\)即可，显然求一下每个点到根路径异或和，开个桶随便搞搞就完事了

对于\(w\leq 10^8\)，我们不能再状压成二进制了，考虑对每个质因子设置一个\(\rm unsigned\ long \ long\)范围内的权值，一条边的权值就是所有出现次数为奇数的质因子权值的异或和，还是求有多少条路径异或为\(0\)

之后就被卡了，各种换随机种子也只有90

代码

#include 
    
     #define re register#define LL long long#define max(a, b) ((a) > (b) ? (a) : (b))#define ull unsigned long longinline int read() {    char c = getchar();    int x = 0;    while (c < '0' || c > '9') c = getchar();    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - 48, c = getchar();    return x;}const int maxn = 1e5 + 5;struct E {    int v, nxt;    ull w;} e[maxn << 1];int n, num, T, f[10005], p[10005];int head[maxn], xx[maxn], yy[maxn], ww[maxn];ull w[10005], pre[maxn];std::map
     
       ma;std::map
      
        tax;inline void add(int x, int y, ull w) {    e[++num].v = y;    e[num].nxt = head[x];    head[x] = num;    e[num].w = w;}inline ull Rand() {    return (((ull)rand() % 32768ll) << 45ll) + (((ull)rand() % 32768ll) << 30ll) +           (((ull)rand() % 32768ll) << 15ll) + ((ull)rand() % 32768ll);}void dfs(int x, int fa) {    for (re int i = head[x]; i; i = e[i].nxt) {        if (e[i].v == fa)            continue;        pre[e[i].v] = pre[x] ^ e[i].w;        dfs(e[i].v, x);    }}int main() {    srand(19260817);    n = read();    for (re int i = 1; i < n; i++) xx[i] = read(), yy[i] = read(), ww[i] = read(), T = max(T, ww[i]);    T = std::ceil(std::sqrt(T));    for (re int i = 2; i <= T; i++) {        if (!f[i])            p[++p[0]] = i, w[p[0]] = Rand();        for (re int j = 1; j <= p[0] && p[j] * i <= T; ++j) {            f[p[j] * i] = 1;            if (i % p[j] == 0)                break;        }    }    for (re int i = 1; i < n; i++) {        int now = 0;        for (re int t = 0, j = 1; j <= p[0]; ++j, t = 0) {            if (ww[i] % p[j])                continue;            while (ww[i] % p[j] == 0) ww[i] /= p[j], t ^= 1;            now ^= (t * w[j]);            if (ww[i] == 1)                break;        }        if (ww[i] != 1) {            if (!ma[ww[i]])                ma[ww[i]] = Rand();            now ^= ma[ww[i]];        }        add(xx[i], yy[i], now), add(yy[i], xx[i], now);    }    dfs(1, 0);    LL ans = 0;    for (re int i = 1; i <= n; i++) ans += tax[pre[i]], tax[pre[i]]++;    printf("%lld\n", 2ll * ans);    return 0;}