之前的

之前发的讨论(没一个人回)

现在的代码

提交记录

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

inline int read(){
	int x = 0;
	char ch = getchar();
	while(!('0' <= ch && ch <= '9')){
		ch = getchar();
	}
	while('0' <= ch && ch <= '9'){
		x = x * 10 + (ch - '0') ;
		ch = getchar();
	}
	return x;
}

inline void write(const __int128 x){
	if(x > 9){
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

const int MAXN = 1e5 + 1;

int n, m;
int d[MAXN];
int ind[MAXN], outd[MAXN];

int head, tail;
int q[MAXN];

vector<int> G[MAXN];

__int128 gcd(__int128 i, __int128 j){
	return j == 0 ? i : gcd(j, i % j);
}

__int128 lcm(__int128 i, __int128 j){
	return i / gcd(i, j) * j;
}

struct Drainage_Node_Data{
	__int128 numerator, denominator;
	
	Drainage_Node_Data operator + (const Drainage_Node_Data& j){
		const Drainage_Node_Data i = *this;
		__int128 Lcm = lcm(i.denominator, j.denominator);
		__int128 a = Lcm / i.denominator, b = Lcm / j.denominator;
		Drainage_Node_Data Res;
		Res.denominator = Lcm;
		Res.numerator = i.numerator * a + j.numerator * b;
		__int128 Gcd = gcd(Res.numerator, Res.denominator);
		Res.numerator = Res.numerator / Gcd;
		Res.denominator = Res.denominator / Gcd;
		return Res;
	}
	
	Drainage_Node_Data operator / (const int& j){
		const Drainage_Node_Data i = *this;
		__int128 b = i.denominator * j;
		__int128 Gcd = gcd(i.numerator, b);
		Drainage_Node_Data Res;
		Res.numerator = i.numerator / Gcd;
		Res.denominator = b / Gcd;
		return Res;
	}
};

Drainage_Node_Data dp[MAXN];

void print(Drainage_Node_Data i){
	write(i.numerator);
	putchar(' ');
	write(i.denominator);
}

void Kahn(){
	head = 1, tail = 0;
	for(int i = 1; i <= n; i++){
		if(ind[i] == 0){
			q[++tail] = i;
			dp[i] = Drainage_Node_Data{1, 1};
		}else{
			dp[i] = Drainage_Node_Data{0, 1};
		}
	}
	while(head <= tail){
		int u = q[head++];
		for(int v : G[u]){
			dp[v] = dp[v] + dp[u] / d[u];
			if(--ind[v] == 0){
				q[++tail] = v;
			}
		}
	}
}

int main(){
//	freopen("water.in", "r", stdin);
//	freopen("water.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	n = read(), m = read();
	for(int u = 1; u <= n; u++){
		d[u] = read();
		for(int j = 1, v; j <= d[u]; j++){
			v = read();
			G[u].push_back(v);
			ind[v]++;
			outd[u]++;
		}
	}
	Kahn();
	for(int i = 1; i <= n; i++){
		if(outd[i] == 0){
			print(dp[i]);
			putchar('\n');
		}
	}
	
	return 0;
}