聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。
以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。
5 1 2 1 1 3 2 1 4 1 2 5 3
13/25
【样例说明】
13组点对分别是(1,1) (2,2) (2,3) (2,5) (3,2) (3,3) (3,4) (3,5) (4,3) (4,4) (5,2) (5,3) (5,5)。
【数据规模】
对于100%的数据，n<=20000。
1778914
| ksq2013 | 2152 | Accepted | 2796 kb | 356 ms | C++/Edit | 1786 B | 2017-01-07 17:08:54 |
点分治模板题目，按要求求解即可
#include<stdio.h> #include<string.h> #define N 20010 #define dmax(x,y) ((x)>(y)?(x):(y)) inline int Rin(){ int x=0,c=getchar(),f=1; for(;c<48||c>57;c=getchar()) if(!(c^45))f=-1; for(;c>47&&c<58;c=getchar()) x=(x<<1)+(x<<3)+c-48; return x*f; } inline int gcd(int x,int y){ int k; while(y){ k=x%y; x=y; y=k; } return x; } bool vis[N]; int n,fst[N],ecnt,ans,root,sum,d[N],ind[6],f[N],size[N]; struct edge{ int v,w,nxt; }e[N<<1]; inline void link(int x,int y,int w){ e[++ecnt].v=y; e[ecnt].w=w; e[ecnt].nxt=fst[x]; fst[x]=ecnt; } void getroot(int x,int fa){ f[x]=0; size[x]=1; for(int j=fst[x];j;j=e[j].nxt) if(e[j].v^fa&&!vis[e[j].v]) getroot(e[j].v,x), size[x]+=size[e[j].v], f[x]=dmax(f[x],size[e[j].v]); f[x]=dmax(f[x],sum-size[x]); if(f[x]<=f[root])root=x; } void getdeep(int x,int fa){ ind[d[x]]++; for(int j=fst[x];j;j=e[j].nxt) if(e[j].v^fa&&!vis[e[j].v]) d[e[j].v]=(d[x]+e[j].w)%3, getdeep(e[j].v,x); } int calc(int x,int w){ ind[0]=ind[1]=ind[2]=0,d[x]=w,getdeep(x,0); return ind[1]*ind[2]*2+ind[0]*ind[0]; } void solve(int x){ ans+=calc(x,0),vis[x]=1; for(int j=fst[x];j;j=e[j].nxt) if(!vis[e[j].v]) ans-=calc(e[j].v,e[j].w), sum=size[e[j].v],root=0, getroot(e[j].v,0), solve(root); } int main(){ n=Rin(); for(int i=1;i<n;i++){ int x=Rin(),y=Rin(),w=Rin()%3; link(x,y,w),link(y,x,w); } sum=f[0]=n, getroot(1,0), solve(root); int t=gcd(ans,n*n); printf("%d/%d\n",ans/t,n*n/t); return 0; }
原文：http://www.cnblogs.com/keshuqi/p/6259843.html