Description
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
Solution
一道比较裸的点分
每次用t[i]记录到该点距离模3为i的点个数量
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define MAXN 20005 #define INF 0x3f3f3f3f using namespace std; int n,head[MAXN],siz[MAXN],maxv[MAXN],root=0,tot=0,num=0,cnt=0,t[3],p,q; bool vis[MAXN]; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct Node { int next,to,w; }Edges[MAXN*2]; int gcd(int a,int b){return b?gcd(b,a%b):a;} void addedge(int u,int v,int w) { Edges[cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v; Edges[cnt++].w=w; } void getroot(int u,int f) { siz[u]=1,maxv[u]=0; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==f||vis[v])continue; getroot(v,u); siz[u]+=siz[v],maxv[u]=max(maxv[u],siz[v]); } maxv[u]=max(maxv[u],tot-siz[u]); if(maxv[u]<maxv[root])root=u; } void getdeep(int u,int f,int d) { t[d]++; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==f||vis[v])continue; getdeep(v,u,(d+Edges[i].w)%3); } } int calc(int u,int d) { memset(t,0,sizeof(t)); getdeep(u,0,d); return t[0]*t[0]+t[1]*t[2]*2; } void work(int u) { vis[u]=1;p+=calc(u,0); for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(vis[v])continue; p-=calc(v,Edges[i].w%3); tot=siz[v],root=0; getroot(v,u),work(root); } } int main() { memset(head,-1,sizeof(head)); n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); addedge(u,v,w),addedge(v,u,w); } maxv[0]=INF,tot=n; p=0,q=n*n; getroot(1,0),work(root); int t=gcd(p,q); printf("%d/%d ",p/t,q/t); return 0; }