可能一步步克服恐惧的过程就是成功，所以只管面对恐惧，不思考结果，
24分钟敲模板，这是点分治第一次敲的这么顺利，纪念一下。
洛谷：2634.求距离是三的倍数的点对数
//点分治模板，找有多少点的距离是3的倍数 #include<bits/stdc++.h> using namespace std; #define ll long long const int M=2e4+5; struct Node{int to,nex;ll v;}e[M<<1]; int head[M<<1],cnt=1,n,siz[M],mx,rt,sum,v[M]; ll t[4]; void add(int x,int y,int v){ e[cnt].to=y;e[cnt].v=v;e[cnt].nex=head[x];head[x]=cnt++; e[cnt].to=x;e[cnt].v=v;e[cnt].nex=head[y];head[y]=cnt++; } void getrt(int x,int f){ siz[x]=1;int mm=0; for(int to,i=head[x];~i;i=e[i].nex){ to=e[i].to; if(v[to]||f==to)continue; getrt(to,x); siz[x]+=siz[to]; if(mm<siz[to])mm=siz[to]; } if(mm<sum-siz[x])mm=sum-siz[x]; if(mx>mm)mx=mm,rt=x; } void getdis(int x,int f,ll dis){ t[dis%3]++; for(int to,i=head[x];~i;i=e[i].nex){ to=e[i].to; if(v[to]||to==f)continue; getdis(to,x,dis+e[i].v); } } ll cal(int x,int f,int dis){ t[0]=t[1]=t[2]=0; getdis(x,f,dis); return t[0]*t[0]+t[1]*t[2]*2; } ll slove(int x){ ll res=cal(x,-1,0); v[x]=1; for(int to,i=head[x];~i;i=e[i].nex){ to=e[i].to; if(v[to])continue; res-=cal(to,x,e[i].v); sum=siz[to];mx=0x3f3f3f3f; getrt(to,-1); res+=slove(rt); } return res; } int main(){ memset(head,-1,sizeof(head)); scanf("%d",&n); for(int x,y,v,i=1;i<n;i++)scanf("%d%d%d",&x,&y,&v),add(x,y,v);//建立边 sum=n;mx=0x3f3f3f3f; getrt(1,-1); ll a=slove(rt),b=n*n; ll c=__gcd(a,b); printf("%lld/%lld",a/c,b/c); return 0; }
