80pts求助
查看原帖
80pts求助
793685
fanyongyuan楼主2023/8/19 17:12
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;

vector<int>vec[100005];
pair<ll,ll>water[100005];
int fa[100005],num[100005];

int find_fa(int i)
{
	if(fa[i]==i)return i;
	else return  fa[i]=find_fa(fa[i]);
}

void pushup(int i)
{
	ll a=__gcd(water[i].second,water[i].first);
	water[i].first/=a;
	water[i].second/=a;
}

void add(int i,ll p,ll q)
{
	if(p==0)return ;
	if(water[i].first==0)
	{
		water[i].first=p;
		water[i].second=q;
	}
	else
	{
		water[i].first=water[i].first*q+p*water[i].second;
	    water[i].second*=q;
	}
	pushup(i);
}

void push(int s,ll p,ll q)
{
	if(num[s])
	{
		q*=num[s];
		for(vector<int>::iterator it=vec[s].begin();it!=vec[s].end();it++)push(*it,p,q);
		water[s].first=0,water[s].second=0;
	}
	else 
	{
		add(s,p,q);
	}
}

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		cin>>num[i];
		for(int j=1;j<=num[i];j++){
			int a;
			cin>>a;
			vec[i].push_back(a);
			fa[a]=i;
		}
	}
	
	for(int i=1;i<=n;i++)fa[i]=find_fa(i);
	for(int i=1;i<=n;i++)
	    if(fa[i]==i)push(i,1,1);
		
	for(int i=1;i<=n;i++)
	    if(vec[i].empty())printf("%lld %lld\n",water[i].first,water[i].second);

	return 0;
}
2023/8/19 17:12
加载中...