这道题是要用高精度吗?第10个点错了
#include<bits/stdc++.h>
#define LL unsigned long long
using namespace std;
LL gcd(LL x,LL y)
{
if(y==0) return x;
else return gcd(y,x%y);
}
struct frac
{
LL x,y;
frac()
{
x=0,y=1;
}
friend frac operator+ (const frac &p,const frac &q)
{
frac ans;
LL t=gcd(p.y,q.y);
ans.x=q.y/t*p.x+p.y/t*q.x;
ans.y=p.y/t*q.y;
t=gcd(ans.x,ans.y);
ans.x/=t,ans.y/=t;
return ans;
}
};
struct edge
{
int v,next;
}e[500010];
int m,n,x,cnt;
int d[100010],ind[100010],head[100010];
frac ans[100010];
queue <int> q;
void addedge(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&d[i]);
for(int j=1;j<=d[i];j++)
{
scanf("%d",&x);
ind[x]++,addedge(i,x);
}
}
for(int i=1;i<=n;i++)
if(ind[i]==0)
q.push(i),ans[i].x=1;
while(!q.empty())
{
int now=q.front();
q.pop();
if(d[now]) ans[now].y*=d[now];
for(int i=head[now];i;i=e[i].next)
{
int v=e[i].v;
ans[v]=ans[v]+ans[now];
ind[v]--;
if(ind[v]==0)
q.push(v);
}
}
for(int i=1;i<=n;i++)
if(d[i]==0)
printf("%llu %llu\n",ans[i].x,ans[i].y);
}