lp2634 国家集训队 聪聪可可

这一题本质上和那道「模板 点分治1」是一样的，直接一边统计一边取模即可。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

typedef long long ll;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline ll gcd(ll A,ll B){
	return B?gcd(B,A%B):A;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[20005],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et; 
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,W);
}

int n,rt=0,s;
int vis[20005],sz[20005],mx[20005];
inline void dfs0(int X,int FA){
	sz[X]=1,mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],s-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
	}
}
int exist[3],dis[20005],st[20005],st2[20005],tp=0,tp2=0;
ll ans=0;
inline void dfs2(int X,int FA){
	st[++tp]=dis[X];
	Fv(i,X){
		if(e[i].v==FA||vis[e[i].v]){
			continue;
		}
		dis[e[i].v]=dis[X]+e[i].w;
		dfs2(e[i].v,X);
	}
}
inline void calc(int X){
	tp2=0;
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		tp=0;
		dis[e[i].v]=e[i].w;
		dfs2(e[i].v,X);
		for(int j=1;j<=tp;++j){
			ans+=exist[(3-st[j]%3)%3];
		}
		for(int j=1;j<=tp;++j){
			st2[++tp2]=st[j];
			++exist[st[j]%3];
		}
	}
	for(int i=0;i<3;++i){
		exist[i]=0;
	}
}

inline void dfs1(int X){
	exist[0]=vis[X]=1;
	calc(X);
	Fv(i,X){
		if(vis[e[i].v]){
			continue;
		}
		rt=0;
		s=sz[X];
		dfs0(e[i].v,X);
		dfs1(rt);
	}
}

void init(){
	scanf("%d",&n);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	} 
	rt=0,mx[0]=n;
	dfs0(1,0);
	dfs1(1);
	ans=(ans<<1)+n;
	ll g=gcd(ans,n*n);
	printf("%lld/%lld\n",ans/g,(n*n)/g);
}

int main(){
	init();
	return 0;
}