原题目：

在人类和跳蚤的战争初期，人们凭借着地理优势占据了上风——即使是最强壮的跳蚤，也无法一下越过那一堵坚固的城墙。

在经历了惨痛的牺牲后，跳蚤国王意识到再这样下去，跳蚤国必败无疑。然而为了震慑跳蚤国的老冤家——猴族，跳蚤国那世界上最跳的坦克只能留在跳蚤国本土，无法派上用场。

于是跳蚤国王决定利用跳蚤国最尖端的技术，创造出最强的跳蚤来挽回败局。

为了避免这样的低级失误，跳蚤国王决定使用机器来帮助他创造跳蚤。他把它拥有的

跳蚤国王的机器会使用这样的方式来创造跳蚤：跳蚤国王需要选择两个不同的容器

每一条橡胶软管都有一个耐久度

现在，跳蚤国王想要知道有多少种不同的制造方案是安全的。但是因为跳蚤国王日理万机，所以他让你——一个刚刚被抓来的人类俘虏来帮他计算答案。

两个制造方案是不同的当且仅当

输入格式

第一行两个正整数

以下

输出格式

输出一行一个整数表示制造方案数。

样例一

input

1 2 2

1 3 6

1 4 2

4 5 3

output

题目大意就是给你一棵有边权的树，让你求其中有多少个点对路径上的边权积为完全平方数。
一开始看这个一脸不可做啊……树剖也不行，点分治貌似行，但是我不会写啊……（貌似其实也不行）
（高阶百度搜索技巧）
其实当传统做法不行的时候，可以反过来看看题目本身的特殊条件。注意到他要求边权积为完全平方数，可以想到其中每个质因子都出现了偶数次。
考虑用什么办法可以判断某个数出现了偶数次，发现偶数个相同的数异或起来必定是0。
为了避免和其他数重复，可以把每个质数哈希一下（这里我懒了，直接用的rand()，导致分数也是rand(60,100)）。
所以问题就转化为了求树上异或和为零的路径的个数。
易得当且仅当两个节点到根节点的异或和相等时它们间路径的异或和为0。
所以就可以直接一次dfs求出了^_^
时间复杂度：O(n)（预处理比较麻烦，貌似很多学长被卡常了）
代码：

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cstdio>
 6 #include<ctime>
 7 #include<cmath>
 8 #include<map>
 9 using namespace std;
10 typedef long long ll;
11 struct edge{
12     int v,next;
13     ll w;
14 }a[300001];
15 int n,u,v,tot=0,pr=0,head[100001],pri[100001];
16 ll w,num[100001],ans=0;
17 map<ll,ll>pp;
18 bool isp[100001];
19 ll rd(){
20     return (ll)((ll)(rand())<<30)+rand();
21 }
22 void getprime(){
23     for(int i=2;i<=100000;i++){
24         if(!isp[i])pri[++pr]=i;
25         for(int j=1;j<=pr&&i*pri[j]<=100000;j++){
26             isp[i*pri[j]]=1;
27             if(!(i%pri[j]))break;
28         }
29     }
30     for(int i=1;i<=pr;i++){
31         pp[pri[i]]=rd();
32     }
33 }
34 void add(int u,int v,ll w){
35     a[++tot].v=v;
36     a[tot].w=w;
37     a[tot].next=head[u];
38     head[u]=tot;
39 }
40 void dfs(int u,int fa){
41     for(int tmp=head[u];tmp!=-1;tmp=a[tmp].next){
42         int v=a[tmp].v;
43         if(v==fa)continue;
44         num[v]=num[u]^a[tmp].w;
45         dfs(v,u);
46     }
47 }
48 int main(){
49     memset(head,-1,sizeof(head));
50     memset(isp,0,sizeof(isp));
51     srand(time(NULL));
52     scanf("%d",&n);
53     getprime();
54     for(int i=1;i<n;i++){
55         scanf("%d%d%lld",&u,&v,&w);
56         int ww=0;
57         for(int j=1;j<=pr&&pri[j]*pri[j]<=w;j++){
58             while(!(w%pri[j])){
59                 w/=pri[j];
60                 ww^=pp[pri[j]];
61             }
62         }
63         if(w!=1){
64             if(!pp[w])pp[w]=rd();
65             ww^=pp[w];
66         }
67         add(u,v,ww);
68         add(v,u,ww);
69     }
70     num[1]=0;
71     dfs(1,-1);
72     sort(num+1,num+n+1);
73     for(int i=1,j;i<=n;i=j){
74         j=i;
75         while(num[i]==num[j]&&j<=n)j++;
76         ans+=(ll)(j-i)*(j-i-1);
77     }
78     printf("%lld",ans);
79     return 0;
80 }

View Code