P2634 [国家集训队] 聪聪可可
题目描述
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。
他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画nnn个“点”，并用n−1n-1n−1条“边”把这nnn个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随机选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是333的倍数，则判聪聪赢，否则可可赢。
聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
输入格式
输入的第111行包含111个正整数nnn。后面n−1n-1n−1行，每行333个整数x,y,wx,y,wx,y,w，表示xxx号点和yyy号点之间有一条边，上面的数是www。
输出格式
以即约分数形式输出这个概率（即a/b的形式，其中aaa和bbb必须互质。如果概率为111，输出1/1）。
输入输出样例 #1
输入 #1
5 1 2 1 1 3 2 1 4 1 2 5 3输出 #1
13/25说明/提示
【样例说明】
131313组点对分别是(1,1)(1,1)(1,1)，(2,2)(2,2)(2,2)，(2,3)(2,3)(2,3)，(2,5)(2,5)(2,5)，(3,2)(3,2)(3,2)，(3,3)(3,3)(3,3)，(3,4)(3,4)(3,4)，(3,5)(3,5)(3,5)，(4,3)(4,3)(4,3)，(4,4)(4,4)(4,4)，(5,2)(5,2)(5,2)，(5,3)(5,3)(5,3)，(5,5)(5,5)(5,5)。
【数据规模】
对于100%100\%100%的数据，n≤2×104n\leq 2 \times 10^4n≤2×104。
C++实现
#include<bits/stdc++.h>usingnamespacestd;inlineintread(){ints=0,f=1;charch=getchar();while(!isdigit(ch))f=(ch=='-'?-1:1),ch=getchar();while(isdigit(ch))s=(s<<1)+(s<<3)+(ch&15),ch=getchar();returns*f;}intn,f[20005][3],u,v,w,ans,m;vector<int>nxt[20005],val[20005];inlinevoiddfs(intnow,intfa){f[now][0]=1;vector<int>::iterator iv=val[now].begin();for(vector<int>::iterator it=nxt[now].begin();it!=nxt[now].end();++it){if((*it)==fa){++iv;continue;}dfs((*it),now);for(inti=0;i<3;++i)ans+=f[(*it)][i]*f[now][(3-(((i+(*iv))%3+3)%3))%3]*2;for(inti=0;i<3;++i)f[now][((i+(*iv))%3+3)%3]+=f[(*it)][i];++iv;}}inlineintgcd(inta,intb){returnb==0?a:gcd(b,a%b);}intmain(){n=read();for(inti=1;i<n;++i){u=read();v=read();w=read();nxt[u].push_back(v);val[u].push_back(w);nxt[v].push_back(u);val[v].push_back(w);}ans=n;dfs(1,-1);m=n*n;printf("%d/%d",ans/gcd(ans,m),m/gcd(ans,m));return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
