当前位置：首页 > news >正文

打卡信奥刷题（2629）用C++实现信奥题 P2634 [国家集训队] 聪聪可可

news 2026/5/11 22:01:52

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;}