题解

#include<iostream>
#define ll unsigned long long
using namespace std;
int n,m,to[100001][6],rd[100001];
int stk[100001],top;
ll pw[6][1001];
ll qpw(ll x,inlinet y){  
	if(pw[x][y]==0) return pw[x][y]=qpw(x,y-1)*x;
	else return pw[x][y];
}
struct num{  
	int a,b,c;
	num(){
		a=b=c=0;
		return;
	}
};
struct big_num{ 
	int x[51],len;
	void operator=(ll a){
		len=-1;
		while(a) x[++len]=a%10,a/=10;
		return;
	}
	void write(){
		for(int i=len;i>=0;i-=1) cout<<x[i];
		cout<<'\n';
		return;
	}
};
big_num operator*(big_num a,big_num b){  
	big_num c;
	int z=0,l,r;
	c.len=a.len+b.len;
	for(int i=0;i<=c.len;i+=1){
		c.x[i]=z;
		l=max(0,i-b.len); r=min(i,a.len);
		for(int j=l;j<=r;j+=1){
			c.x[i]+=a.x[j]*b.x[i-j];
		}
		z=c.x[i]/10;
		c.x[i]%=10;
	}
	while(z) c.x[++c.len]=z%10,z/=10;
	return c;
}
struct frac{
	ll p;
	num q;
	void operator=(ll x){
		p=x;
		return;
	}
	void deal(){ 
		while(q.a&&p%2llu==0llu){
			p/=2llu;
			q.a-=1;
		}
		while(q.b&&p%3llu==0llu){
			p/=3llu;
			q.b-=1;
		}
		while(q.c&&p%5llu==0llu){
			p/=5llu;
			q.c-=1;
		}
		return;
	}
	void write(){
		big_num x,y;
		x=qpw(2ll,q.a); y=qpw(3ll,q.b);
		x=x*y; y=qpw(5ll,q.c); x=x*y;
		cout<<p<<' ';
		x.write();
		return;
	}
}f[100001];
frac operator/(frac x,int y){  
	if(y==2) x.q.a+=1;
	if(y==3) x.q.b+=1;
	if(y==4) x.q.a+=2;
	if(y==5) x.q.c+=1;
	x.deal();  
	return x;
}
frac operator+(frac x,frac y){ 
	frac z;
	ll v=x.p,w=y.p;
	z.p=0llu;
	if(x.q.a>=y.q.a) w*=qpw(2llu,x.q.a-y.q.a);
	else v*=qpw(2llu,y.q.a-x.q.a);
	if(x.q.b>=y.q.b) w*=qpw(3llu,x.q.b-y.q.b);
	else v*=qpw(3llu,y.q.b-x.q.b);
	if(x.q.c>=y.q.c) w*=qpw(5llu,x.q.c-y.q.c);
	else v*=qpw(5llu,y.q.c-x.q.c);
	z.p=v+w;
	z.q.a=max(x.q.a,y.q.a);
	z.q.b=max(x.q.b,y.q.b);
	z.q.c=max(x.q.c,y.q.c);
	z.deal();  //约分
	return z;
}
int main(){
	int x,y;
	pw[2][0]=pw[3][0]=pw[5][0]=1llu;
	cin>>n>>m;
	for(int i=1;i<=n;i+=1){
		if(i<=m) f[i]=1llu;  
		else f[i]=0llu;
		cin>>to[i][0];
		for(int j=1;j<=to[i][0];j+=1){
			cin>>to[i][j];
			rd[to[i][j]]+=1;
		}
	}
	for(int i=1;i<=n;i+=1){
		if(!rd[i]) stk[++top]=i;
	}
	while(top){ 
		x=stk[top--];
		if(to[x][0]) f[x]=f[x]/to[x][0];
		for(int i=1;i<=to[x][0];i+=1){
			y=to[x][i];
			rd[y]-=1;
			if(!rd[y]) stk[++top]=y;
			f[y]=f[x]+f[y];
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i+=1){
		if(!to[i][0]) f[i].write();  
	}
	return 0;
}

时间内存直接击败法神