BZOJ 2152 聪聪可可 点分治

https://www.lydsy.com/JudgeOnline/problem.php?id=2152

思路：其实就是求满足两点之间的路径长为 $3$的倍数的点对数，算是点分治的模板题。注意 $(x,y)$和 $(y,x)$算做两次，且同一个点可以同时被选中。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;const int maxn=2e4+5;struct Edge
{int to,nxt,dis;
}edge[maxn<<1];ll re; //记录答案
int n,tot;
int head[maxn],dis[maxn],siz[maxn],vis[maxn];
ll cnt[3];inline void addedge(int u,int v,int d)
{edge[++tot].to=v,edge[tot].nxt=head[u],edge[tot].dis=d,head[u]=tot;
}struct Tree
{int n,rt,num;void dfs(int u,int fa){siz[u]=1;int MAX=0;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(v==fa||vis[v])continue;dfs(v,u);siz[u]+=siz[v];MAX=max(MAX,siz[v]);}MAX=max(MAX,n-siz[u]);if(MAX<num)num=MAX,rt=u;}int getrt(int x){rt=0,num=INF;dfs(x,0);return rt;}
}tree;void getdis(int u,int fa)
{++cnt[dis[u]%3];for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(v==fa||vis[v])continue;dis[v]=dis[u]+edge[i].dis;getdis(v,u);}
}ll cal(int u,int val)
{dis[u]=val,cnt[0]=cnt[1]=cnt[2]=0;getdis(u,0);ll ans=0;ans+=cnt[0]*cnt[0];ans+=cnt[1]*cnt[2]*2;return ans;
}void work(int u)
{vis[u]=1;re+=cal(u,0);for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(vis[v])continue;re-=cal(v,edge[i].dis);tree.n=siz[v];work(tree.getrt(v));}
}ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);
}int main()
{while(~scanf("%d",&n)){tot=0;memset(head,0,sizeof(head));memset(vis,0,sizeof(vis));int u,v,w;for(int i=1;i<n;i++){scanf("%d%d%d",&u,&v,&w);addedge(u,v,w),addedge(v,u,w);}re=0,tree.n=n;work(tree.getrt(1));ll tmp=n*n;ll GCD=gcd(tmp,re);re/=GCD,tmp/=GCD;printf("%lld/%lld\n",re,tmp);}return 0;
}