P2634 TLE 40分，答案对的。之前用树形dp过了，为什么点分治过不了。

#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int rd(){
	ri res=0,f=1;register char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())res=(res<<1)+(res<<3)+ch-48;
	return res*f;
}
int n,dep[20005],f[20005],vis[20005],sz[20005],rt,ans;
int hd[20005],cnt,now,nxt[40005],to[40005],vl[40005];
void add(int x,int y,int z){to[++cnt]=y;vl[cnt]=z;nxt[cnt]=hd[x];hd[x]=cnt;}
void zx(int k,int fa){
	f[k]=0;sz[k]=1;
	for(ri i=hd[k],j;i;i=nxt[i])
	if(!vis[j=to[i]]&&j!=fa){
		zx(j,k);sz[k]+=sz[j];
		f[k]=max(f[k],sz[j]);
	}
	f[k]=max(f[k],now-sz[k]);
	if(f[k]<f[rt])rt=k;
}
void ds(int k,int fa,int val){
	dep[val]++;
	for(ri i=hd[k],j;i;i=nxt[i])
	if(!vis[j=to[i]]&&j!=fa){
		zx(j,k);sz[k]+=sz[j];
		f[k]=max(f[k],sz[j]);
		ds(j,k,(val+vl[i])%3);
	}
}
int calc(int k,int val){
	dep[0]=dep[1]=dep[2]=0;ds(k,0,val%3);
	return dep[0]*dep[0]+2*dep[1]*dep[2];
}
void fz(int k){
	vis[k]=1;ans+=calc(k,0);
	for(ri i=hd[k],j;i;i=nxt[i])
	if(!vis[j=to[i]]){
		ans-=calc(j,vl[i]);
		rt=0;now=sz[j];
		zx(j,0);fz(rt);
	}
}
int main(){
	n=rd();
	for(ri i=1,x,y,z;i<n;++i){
		x=rd();y=rd();z=rd();
		add(x,y,z);add(y,x,z);
	}
	now=f[0]=n;zx(1,0);fz(rt);
	n*=n;rt=__gcd(ans,n);
	printf("%d/%d",ans/rt,n/rt);
	return 0;
}