来自FallDream的博客，未经允许，请勿转载， 谢谢。
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
n<=20000 0.3s
点分治练手题..
#include<iostream> #include<cstdio> #define MN 20000 #define INF 2000000000 #define ll long long using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,head[MN+5],cnt=0,rt,mn,size[MN+5],tot,mx[MN+5],dep[MN+5],num[MN+5]; struct edge{int to,next,w;}e[MN*2+5]; bool b[MN+5]; ll ans=0; inline void ins(int f,int t,int w) { e[++cnt]=(edge){t,head[f],w};head[f]=cnt; e[++cnt]=(edge){f,head[t],w};head[t]=cnt; } void getrt(int x,int f) { for(int i=head[x];i;i=e[i].next) if(!b[e[i].to]&&e[i].to!=f) getrt(e[i].to,x); int sz=max(mx[x],tot-size[x]); if(sz<mn) mn=sz,rt=x; } void dfs(int x,int f) { size[x]=1;mx[x]=0;num[dep[x]]++; for(int i=head[x];i;i=e[i].next) if(!b[e[i].to]&&e[i].to!=f) { dep[e[i].to]=(dep[x]+e[i].w)%3; dfs(e[i].to,x); size[x]+=size[e[i].to]; if(size[e[i].to]>mx[x]) mx[x]=size[e[i].to]; } } void solve(int x) { b[x]=1;dep[x]=0;int A=1,B=0,C=0; for(int i=head[x];i;i=e[i].next) if(!b[e[i].to]) { num[0]=num[1]=num[2]=0; dep[e[i].to]=e[i].w;dfs(e[i].to,x); ans+=num[0]*A+num[1]*C+num[2]*B; A+=num[0];B+=num[1];C+=num[2]; } for(int i=head[x];i;i=e[i].next) if(!b[e[i].to]) { mn=INF;tot=size[e[i].to]; getrt(e[i].to,x); solve(rt); } } ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);} int main() { tot=n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read()%3; ins(u,v,w); } dfs(1,0);mn=INF;getrt(1,0); solve(rt);ans=ans*2+n;ll cou=1LL*n*n; ll g=gcd(ans,cou); ans/=g;cou/=g; printf("%lld/%lld",ans,cou); return 0; }