题解

拓扑排序水题，要是没了高精度它也就只能标黄了。（__int128 只能在非NOI环境中使用）
如果一个点所有污水都流进后才能流出，这可以使用拓扑排序实现。
记录下入度，流进污水就把入度-1，入度为0是就把污水排出。
然后实现一下分数加和除即可。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
void print(__int128 &a){
	char buf[55];
	int len = 0;
	while(a){
		buf[++len] = a % 10;
		a /= 10;
	}
	for(int i = len; i; i--) cout << char(buf[i] + '0');
}
#define int __int128
struct node{//分数
	int x, y;//会爆long long，所以应使用高精度/__int128
	void operator += (node b){
		x = x * b.y + y * b.x;
		y = y * b.y;
		int tmp = __gcd(x, y);
		x /= tmp, y /= tmp;
	}
	node operator / (int b){
		node ans = *this;
		int tmp = __gcd(x, b);
		ans.x /= tmp, b /= tmp;
		ans.y *= b;
		return ans;
	}
}a[100005];
#undef int
int n, m;
vector <int> v[100005];
int in[100005];
queue <int> q;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		a[i].y = 1;
		int len;
		cin >> len;
		v[i].resize(len);
		for(int j = 0; j < len; j++) cin >> v[i][j], in[v[i][j]]++;
	}
	for(int i = 1; i <= m; i++){
		a[i].x = 1;
	}
	for(int i = 1; i <= n; i++){
		if(!in[i]) q.push(i);
	}
	while(!q.empty()){
		int head = q.front();
		q.pop();
		for(int i:v[head]){
			a[i] += a[head] / v[head].size();
			if(!(--in[i])) q.push(i);
		}
	}
	for(int i = 1; i <= n; i++){
		if(v[i].size() == 0){
			print(a[i].x);
			cout << ' ';
			print(a[i].y);
			cout << '\n';
		}
	}
	

	return 0;
}

时间复杂度 $O(\sum d_i)$。