和之前的模板题相比，只需要更改getdis这个函数即可，这个函数所做的处理是，求出以参数u为root时满足条件的情况数目。这里是问两点之间的距离是否能被3整除。所以直接讨论三种情况的数目就好了。
1、能整除3的路径数 用sum0计数
2、除3余1的路径数 用sum1计数
3、除3余2的路径数 用sum2计数
最后的答案就是sum1*sum2+sum2*sum1+sum3*sum3 / n*n 再化简一下就是答案
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #define maxn 20002 #define INF 2147483646 #define ll long long using namespace std; ll sum[3]; inline int gi()//输入挂 { int date = 0,m = 1; char ch = 0; while(ch!='-'&&(ch<'0'||ch>'9'))ch = getchar(); if(ch=='-'){m = -1; ch = getchar();} while(ch>='0' && ch<='9') { date = date*10+ch-'0'; ch = getchar(); }return date*m; } inline void write(ll qw) //输出挂 { if(qw<0){putchar('-'); qw = -qw;} if(qw>9)write(qw/10); putchar(qw%10+'0'); } struct node{int to,next,len;}t[2*maxn+5]; int head[maxn+5]; int sim[maxn+5],mxson[maxn+5]; bool vis[maxn+5]; int MX,root,summar; ll ans; int n,k,cnt,S; void addedge(int u,int v,int l) //存图 { cnt ++; t[cnt].to = v; t[cnt].next = head[u]; t[cnt].len = l; head[u] = cnt; return; } void getroot(int u,int fa) //找重心函数 { sim[u] = 1; mxson[u] = 0; for(int i = head[u];i;i = t[i].next) { int v = t[i].to; if(v == fa || vis[v])continue; getroot(v,u); sim[u] = sim[u] + sim[v]; mxson[u] = max(sim[v],mxson[u]); } mxson[u] = max(mxson[u],S-sim[u]); if(mxson[u]<MX){root = u;MX = mxson[u];} } void getdis(int u,int fa,int dist) //计算多统计了的 子树中满足条件的情况 把到u点的距离存到dis数组里去 { sum[dist%3]++; for(int i = head[u];i;i=t[i].next) { int v = t[i].to; if(vis[v]||v == fa)continue; getdis(v,u,(dist+t[i].len)%3); } return; } ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} int consolate(int sta,int len1) //计算当前满足条件情况的数目 { sum[0] = sum[1] = sum[2] = 0; getdis(sta,0,len1); ll now = 2*sum[1]*sum[2] + sum[0]*(sum[0]-1) + sum[0]; return now; } void Divide(int tr) //分治函数 { ans = ans + consolate(tr,0); vis[tr] = true; for(int i = head[tr];i;i = t[i].next) { int v = t[i].to; if(vis[v])continue; ans = ans - consolate(v,t[i].len); S = sim[v]; root = 0; MX = INF; getroot(v,0); Divide(root); } return; } int main() { int u,v,l; n = gi(); cnt = 0; memset(head,0,sizeof(head)); for(int i = 1; i <= n - 1; i ++) { u = gi(); v = gi(); l = gi(); addedge(u,v,l); addedge(v,u,l); } ans = 0; memset(vis,0,sizeof(vis)); MX = INF ; S = n; getroot(1,0); Divide(root); ll gyz=gcd(n*n,ans); write(ans/gyz);putchar('/');write(n*n/gyz); return 0; }