宜宾建功路桥建设有限公司网站,外贸石材网站,c2c交易是什么意思,asp.net网站建设项目实战资料题目描述 聪聪和可可是兄弟俩#xff0c;他们俩经常为了一些琐事打起来#xff0c;例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑#xff08;可是他们家只有一台电脑#xff09;……遇到这种问题#xff0c;一般情况下石头剪刀布就好了#xff0c;可是他们…题目描述 聪聪和可可是兄弟俩他们俩经常为了一些琐事打起来例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑可是他们家只有一台电脑……遇到这种问题一般情况下石头剪刀布就好了可是他们已经玩儿腻了这种低智商的游戏。 他们的爸爸快被他们的争吵烦死了所以他发明了一个新游戏由爸爸在纸上画n个“点”并用n-1条“边”把这n个“点”恰好连通其实这就是一棵树。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点当然他们选点时是看不到这棵树的如果两个点之间所有边上数的和加起来恰好是3的倍数则判聪聪赢否则可可赢。 聪聪非常爱思考问题在每次游戏后都会仔细研究这棵树希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。 输入输出格式 输入格式 输入的第1行包含1个正整数n。后面n-1行每行3个整数x、y、w表示x号点和y号点之间有一条边上面的数是w。 输出格式 以即约分数形式输出这个概率即“a/b”的形式其中a和b必须互质。如果概率为1输出“1/1”。 输入输出样例 输入样例#1 复制 5
1 2 1
1 3 2
1 4 1
2 5 3 输出样例#1 复制 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%的数据n20000。 题解 然后从今天开始学习点分 这应该算是个板子 先用点分计算出路径长度把路径长度对$%3$然后用$sum[1],sum[2],sum[0]$表示模数是$1,2,3$的情况的总数那么就是$anssum[1]*sum[2]*2sum[0]*sum[0]$最后答案就是$ans/(n*n)$ 1 //minamoto2 #includeiostream3 #includecstdio4 #define ll long long5 #define inf 0x3f3f3f3f6 #define getc() (p1p2(p2(p1buf)fread(buf,1,121,stdin),p1p2)?EOF:*p1)7 char buf[121],*p1buf,*p2buf;8 templateclass Tinline bool cmax(Ta,const Tb){return ab?ab,1:0;}9 inline int read(){
10 #define num ch-0
11 char ch;bool flag0;int res;
12 while(!isdigit(chgetc()))
13 (ch-)(flagtrue);
14 for(resnum;isdigit(chgetc());resres*10num);
15 (flag)(res-res);
16 #undef num
17 return res;
18 }
19 char sr[121],z[20];int C-1,Z;
20 inline void Ot(){fwrite(sr,1,C1,stdout),C-1;}
21 inline void print(int x){
22 if(C120)Ot();if(x0)sr[C]45,x-x;
23 while(z[Z]x%1048,x/10);
24 while(sr[C]z[Z],--Z);
25 }
26 const int N20005,mod3;
27 int head[N],Next[N1],edge[N1],ver[N1];ll ans0;
28 int sz[N],son[N],sum[4],vis[N];
29 int size,mx,rt,n,tot;
30 inline void add(int u,int v,int e){
31 ver[tot]v,Next[tot]head[u],head[u]tot,edge[tot]e;
32 ver[tot]u,Next[tot]head[v],head[v]tot,edge[tot]e;
33 }
34 void getrt(int u,int fa){
35 sz[u]1,son[u]0;
36 for(int ihead[u];i;iNext[i]){
37 int vver[i];
38 if(vis[v]||vfa) continue;
39 getrt(v,u);
40 sz[u]sz[v];
41 cmax(son[u],sz[v]);
42 }
43 cmax(son[u],size-sz[u]);
44 if(son[u]mx) mxson[u],rtu;
45 }
46 void query(int u,int fa,int d){
47 sum[d%mod];
48 for(int ihead[u];i;iNext[i]){
49 int vver[i];
50 if(vis[v]||vfa) continue;
51 query(v,u,(dedge[i])%mod);
52 }
53 }
54 ll solve(int rt,int d){
55 sum[0]sum[1]sum[2]0;
56 query(rt,0,d);
57 ll res1ll*sum[1]*sum[2]*21ll*sum[0]*sum[0];
58 return res;
59 }
60 void divide(int u){
61 anssolve(u,0);
62 vis[u]1;
63 for(int ihead[u];i;iNext[i]){
64 int vver[i];
65 if(vis[v]) continue;
66 ans-solve(v,edge[i]);
67 mxinf,rt0,sizesz[v];
68 getrt(v,0);
69 divide(rt);
70 }
71 }
72 inline ll gcd(ll a,ll b){
73 while(b^a^b^a%b);
74 return a;
75 }
76 int main(){
77 nread();
78 for(int i1;in;i){
79 int uread(),vread(),eread();
80 add(u,v,e%3);
81 }
82 mxinf,sizen,ans0,rt0;
83 getrt(1,0),divide(rt);
84 ll pn*n,GCDgcd(ans,p);
85 print(ans/GCD),sr[C]/,print(p/GCD);
86 Ot();
87 return 0;
88 } 转载于:https://www.cnblogs.com/bztMinamoto/p/9476329.html
