不虚就是要AK(czyak.c/.cpp/.pas) 2s 128M by zhb
czy很火。因为又有人说他虚了。为了证明他不虚，他决定要在这次比赛AK。
现在他正在和别人玩一个游戏：在一棵树上随机取两个点，如果这两个点的距离是4的倍数，那么算czy赢，否则对方赢。现在czy想知道他能获胜的概率。
*最终输出的概率要求分数的分子和分母的和尽量小且非负数
本题多组数据。对于每组数据：
第一行一个数n，表示树上的节点个数
接下来n-1条边a,b,c描述a到b有一条长度为c的路径
当n=0时表示读入结束
数据组数不超过10。无部分分
输入数据
5
1 2 1
1 3 2
1 4 1
2 5 3
0
输出数据
7/25
数据范围
数据点 | n的规模 | 数据组数 | 随机生成数据 |
1 | 200 | 1 | 是 |
2 | 200 | 1 | 是 |
3 | 200 | <=3 | 是 |
4 | 2000 | <=3 | 是 |
5 | 2000 | <=3 | 是 |
6 | 2000 | <=5 | 是 |
7 | 20000 | <=5 | 否 |
8 | 20000 | <=5 | 否 |
9 | 20000 | <=10 | 否 |
10 | 20000 | <=10 | 否 |
这题其实跟找距离=K的点对有多少个是一样的，我们把距离全部不断mod4就可以了。
然后就是点分治。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const int N=;
int n,len,ans;
int v[],t[],d[N],first[N],mark[N],size[N];
struct node{
int x,y,d,next;
}a[*N]; void ins(int x,int y,int d)
{
a[++len].x=x;a[len].y=y;a[len].d=d;
a[len].next=first[x];first[x]=len;
} int gcd(int x,int y)
{
if(y==) return x;
return gcd(y,x%y);
} void find_root(int x,int fa,int tot,int &root)
{
size[x]=;
bool bk=;
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(y==fa || mark[y]) continue;
find_root(y,x,tot,root);
size[x]+=size[y];
if(*size[y]>tot) bk=;
}
if(bk && *(tot-size[x])<=tot) root=x;
} void DFS(int x,int fa)
{
int now=((-d[x])%+)%;
ans+=v[now];
t[d[x]]++;
size[x]=;
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(mark[y] || y==fa) continue;
d[y]=(d[x]+a[i].d)%;
DFS(y,x);
size[x]+=size[y];
}
} void dfs(int x,int tot)
{
find_root(x,,tot,x); memset(v,,sizeof(v));
mark[x]=;d[x]=;v[]++; for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(mark[y]) continue;
d[y]=d[x]+a[i].d;
memset(t,,sizeof(t));
DFS(y,x);
for(int j=;j<;j++) v[j]+=t[j];
}
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(mark[y]) continue;
dfs(y,size[y]);
}
} int main()
{
freopen("a.in","r",stdin);
// freopen("czyak.in","r",stdin);
// freopen("czyak.out","w",stdout);
while()
{
scanf("%d",&n);
if(!n) break;
ans=;len=;
memset(mark,,sizeof(mark));
memset(first,,sizeof(first));
for(int i=;i<n;i++)
{
int x,y,d;
scanf("%d%d%d",&x,&y,&d);
d%=;
ins(x,y,d);
ins(y,x,d);
}
// for(int i=1;i<=len;i+=2) printf("%d --> %d %d\n",a[i].x,a[i].y,a[i].d);
dfs(,n);
int fz=*ans+n,fm=n*n;
int g=gcd(fz,fm);
fz/=g;fm/=g;
printf("%d/%d\n",fz,fm);
}
return ;
}