80分求调
查看原帖
80分求调
1491079
yuanlongyu楼主2024/11/25 16:23
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,a[100005][10],ans[100005][3],m;
void gcd(int x)
{
	unsigned long long n=ans[x][1],m=ans[x][2];
	while(n!=0){
		unsigned long long t=m%n;
		m=n,n=t;
	}
	ans[x][1]/=m;ans[x][2]/=m;
}
void dfs(int x)
{
//	cout<<x<<endl;
	for(int i=1;i<=a[x][0];i++)
	{
		ans[a[x][i]][1]=ans[a[x][i]][1]*ans[x][2]*a[x][0]+ans[x][1]*ans[a[x][i]][2];
		ans[a[x][i]][2]*=ans[x][2]*a[x][0];
		gcd(a[x][i]);//cout<<ans[a[x][i]][1]<<ans[a[x][i]][2]<<endl;
		dfs(a[x][i]);
	}
	if(a[x][0]>0)
	{
		ans[x][1]=0;ans[x][2]=1;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i][0]);ans[i][2]=1;
		for(int j=1;j<=a[i][0];j++)scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=m;i++)
	{
		ans[i][1]=1;dfs(i);
	}
	for(int i=1;i<=n;i++)if(a[i][0]==0)printf("%lld %lld\n",ans[i][1],ans[i][2]);
	return 0;
}
2024/11/25 16:23
加载中...