【国家集训队2011】聪聪可可树分治

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

Hint

样例说明：
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)。
数据规模和约定
对于30%的数据，n<=1000　　另有20%的数据，给出的树中每个节点的度不超过2；
对于100%的数据，n<=20000

题解：

此题与统计<=k的路径大致相似只是统计时需统计能被3整除，余1，余2的路径数量，设为res[0、1、2]

然后答案就是res[0]*res[0]+res[1]*res[2]*2

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7  
  8 const int N=20005;
  9  
 10 int read()
 11 {
 12     int str=0;char ch=getchar();
 13     while(ch>'9' || ch<'0')ch=getchar();
 14     while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar();
 15     return str;
 16 }
 17  
 18 int head[N];struct Lin{int next,to,dis;}a[N*2];int num=0;int son[N],f[N]={9999999},sum=0;
 19 bool vis[N];int root=0;int dis[N];int ans=0;
 20 void init(int x,int y,int z)
 21 {
 22     a[++num].next=head[x];
 23     a[num].to=y;
 24     a[num].dis=z;
 25     head[x]=num;
 26 }
 27  
 28 void getroot(int x,int last)
 29 {
 30     son[x]=1;f[x]=0;
 31     int u;
 32     for(int i=head[x];i;i=a[i].next)
 33     {
 34         u=a[i].to;
 35         if(u==last || vis[u])continue;
 36         getroot(u,x);
 37         son[x]+=son[u];
 38         f[x]=max(f[x],son[u]);
 39     }
 40     f[x]=max(f[x],sum-son[x]);
 41     if(f[x]<f[root])root=x;
 42     return ;
 43 }
 44  
 45 int res[5];
 46  
 47 void getdis(int x,int last)
 48 {
 49     int u;
 50     res[dis[x]]++;
 51     for(int i=head[x]; i ;i=a[i].next)
 52     {
 53         u=a[i].to;
 54         if(vis[u] || u==last)continue;
 55         dis[u]=(dis[x]+a[i].dis)%3;
 56         getdis(u,x);
 57     }
 58     return ;
 59 }
 60  
 61 int getans(int x,int dd)
 62 {
 63     res[0]=res[1]=res[2]=0;
 64     dis[x]=dd;
 65     getdis(x,0);
 66     return (res[0]*res[0])+((res[1]*res[2])<<1);
 67 }
 68  
 69 void work(int x)
 70 {
 71     int u;
 72     ans+=getans(x,0);
 73     vis[x]=1;
 74     for(int i=head[x];i;i=a[i].next)
 75     {
 76         u=a[i].to;
 77         if(vis[u])continue;
 78         ans-=getans(u,a[i].dis);
 79         root=0;
 80         sum=son[u];
 81         getroot(u,x);
 82         work(root);
 83     }
 84 }
 85  
 86 int gcd(int x,int y)
 87 {
 88     return (x%y)?gcd(y,x%y):y;
 89 }
 90  
 91 int main()
 92 {
 93     int n;int x,y,z;
 94     n=read();
 95     sum=n;
 96     for(int i=1;i<=n-1;i++)
 97     {
 98         x=read();y=read();z=read()%3;
 99         init(x,y,z);init(y,x,z);
100     }
101     root=0;
102     getroot(1,0);
103     work(root);
104     int ppap=gcd(ans,n*n);
105     printf("%d/%d",ans/ppap,n*n/ppap);
106     return 0;
107 }