只开了long long
先后乘除差别真的这么大嘛?
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
int n,m;
vector<int >edge[100001];
int in[100001]={};
void add(int a,int b)
{
edge[a].push_back(b);
in[b]++;
}
struct ELE
{
long long tot,div;
}node[100001];
long long gcd(long long a,long long b)
{
if(b==0)return a;
return gcd(b,a%b);
}
ELE water_plus(long long tot1,long long div1,long long tot2,long long div2)
{
long long g1=gcd(div1,div2);
long long tot=tot1*(div2/g1)+tot2*(div1/g1);
long long div=div1*(div2/g1);
long long g2=gcd(tot,div);
return ELE{tot/g2,div/g2};
}
void run()
{
priority_queue<int >Q;
for(int i=1;i<=m;i++)
{
Q.push(-i);
node[i].tot=1;
node[i].div=1;
}
for(int i=m+1;i<=n;i++)
{
node[i].tot=0;
node[i].div=1;
}
while(!Q.empty())
{
int cur=-Q.top();
Q.pop();
long long tot1=node[cur].tot;
long long div1=node[cur].div;
int out=edge[cur].size();
long long g=gcd(tot1,div1);
if(out==0)
{
printf("%lld %lld\n",tot1/g,div1/g);
continue;
}
div1=div1*out;
for(int i=0;i<out;i++)
{
int to=edge[cur][i];
node[to]=water_plus(tot1,div1,node[to].tot,node[to].div);
in[to]--;
if(in[to]==0)
Q.push(-to);
}
}
}
int main()
{
// freopen("water.in","r",stdin);
// freopen("water.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int tot;
scanf("%d",&tot);
for(int j=1;j<=tot;j++)
{
int to;
scanf("%d",&to);
add(i,to);
}
}
run();
return 0;
}