C++之路进阶——bzoj2152（聪聪可可）

F.A.Qs	Home	Discuss	ProblemSet	Status	Ranklist	Contest	ModifyUser hyxzc	Logout	捐赠本站

Notice:由于本OJ建立在Linux平台下，而许多题的数据在Windows下制作，请注意输入、输出语句及数据类型及范围，避免无谓的RE出现。

2152: 聪聪可可

Time Limit: 3 Sec Memory Limit: 259 MB
Submit: 1404 Solved: 706
[Submit][Status][Discuss]

Description

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Input

输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。

Output

以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。

Sample Input

5
1 2 1
1 3 2
1 4 1
2 5 3

Sample Output

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。

HINT

Source

代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #define maxn 20010
 6  
 7 using namespace std;
 8  
 9 struct ss
10   {
11     int next;
12     int to;
13     int w;
14   }e[maxn*2];
15    
16 int n,root,sum,ans,f[maxn],t[3],d[maxn],head[maxn],son[maxn],cnt;
17 bool vis[maxn];
18       
19 void insert(int u,int v,int w)
20    {
21     e[++cnt].to=v; e[cnt].next=head[u]; e[cnt].w=w; head[u]=cnt;
22         }
23          
24 int gcd(int a,int b)
25  {
26     return b==0?a:gcd(b,a%b);
27  }
28  
29 void getroot(int x,int fa)
30    {
31      son[x]=1;  
32      f[x]=0;
33      for (int i=head[x];i;i=e[i].next)
34        if (!vis[e[i].to]&&e[i].to!=fa)
35            {
36               getroot(e[i].to,x);
37               son[x]+=son[e[i].to];
38               f[x]=max(f[x],son[e[i].to]);
39               }
40     f[x]=max(f[x],sum-son[x]);
41     if (f[x]<f[root]) root=x;
42     return;       
43    }             
44  
45 int getdeep(int x,int fa)    
46    {
47     t[d[x]]++;
48     for (int i=head[x];i;i=e[i].next)
49        if (!vis[e[i].to]&&e[i].to!=fa)
50           {  
51              d[e[i].to]=(d[x]+e[i].w)%3;
52              getdeep(e[i].to,x);
53              }
54    }
55     
56 int cal(int x,int now)
57    {
58       t[0]=t[1]=t[2]=0;
59       d[x]=now;
60       getdeep(x,0);
61       return t[1]*t[2]*2+t[0]*t[0];
62        }    
63  
64 void work(int x)
65   {
66     vis[x]=1;
67     ans+=cal(x,0);
68     for (int i=head[x];i;i=e[i].next)
69       if (!vis[e[i].to])
70        {
71          ans-=cal(e[i].to,e[i].w);
72          sum=son[e[i].to]; 
73          root=0;
74          getroot(e[i].to,0);
75          work(root);
76          }
77      }   
78       
79 int main()
80   {
81     scanf("%d",&n);
82     for (int i=1;i<n;i++)
83        {
84          int u,v,w;
85          scanf("%d%d%d",&u,&v,&w);     
86          insert(u,v,w%3);
87          insert(v,u,w%3);      
88          }
89     f[0]=sum=n;
90     getroot(1,0);        
91     work(root); 
92     int t=gcd(ans,n*n);
93     printf("%d/%d",ans/t,n*n/t);         
94     return 0;        
95        }