后几个点Wa掉了,输出挺离谱的
不是爆long long的问题
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,m,num[100005],in[100005],x,dx[100005],dy[100005];
queue<int> q;
vector<int> G[100005];
int gcd(int x,int y){
if (!y)return x;
return gcd(y,x%y);
}
signed main(){
scanf("%llu%llu",&n,&m);
for (int i=1;i<=n;i++){
scanf("%llu",&num[i]);
for (int j=1;j<=num[i];j++){
scanf("%llu",&x);
G[i].push_back(x);
in[x]++;
}
}
for (int i=1;i<=n;i++){
if (in[i]==0){
q.push(i);
dx[i]=1;
dy[i]=1;
}else{
dy[i]=1;
dx[i]=0;
}
}
while (!q.empty()){
int x=q.front();
q.pop();
int dxx=dx[x],dyy=dy[x]*G[x].size();
int GCD=gcd(dxx,dyy);
dxx/=GCD;dyy/=GCD;
for (int i=0;i<G[x].size();i++){
int v=G[x][i];
//dx[v]/dy[v]+dxx/dyy=(dxx*dy[v]+dx[v]*dyy)/(dxx*dy[v]);
int to_dx=(dxx*dy[v]+dx[v]*dyy),to_dy=(dyy*dy[v]);
dx[v]=to_dx;dy[v]=to_dy;
int GCD_v=gcd(dx[v],dy[v]);
dx[v]/=GCD_v;dy[v]/=GCD_v;
in[v]--;
if (in[v]==0)q.push(v);
}
}
for (int i=1;i<=n;i++){
if (G[i].size()==0){
printf("%llu %llu\n",dx[i],dy[i]);
}
}
return 0;
}