思路与算法

拓扑顺序传播精确分数，节点水量等分给每条出边。分数相加先约两分母的gcd再计算公分母，使用128位整数并最终约分，按编号输出所有汇点。

正确性说明

DAG拓扑序使处理一个节点前所有入流都已精确相加，等分出流遵守守恒，因此归纳得各汇点正确体积。每条流路最多11条边且每个出度1..5，所有分母均整除60^11，分子不超过m倍此界。先约gcd求lcm避免先乘分母的无谓大中间数，128位足够这些界，约分保证输出互素。

复杂度

O((n+e)*log B)整数步时间、O(n+e)空间，B为128位分子分母界；含邻接表、入度、分数、队列初始化及输出。

易错点

分母为1也输出1；没有水的汇点输出0 1。只用64位或浮点可能丢失精确值，且不能先乘两个大分母再约分。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using I = __int128;
I gcd1(I a, I b) {
    while (b) {
        I t = a % b;
        a = b;
        b = t;
    }
    return a;
}
struct F {
    I a = 0, b = 1;
    void norm() {
        I g = gcd1(a, b);
        a /= g;
        b /= g;
    }
    void add(F x) {
        I g = gcd1(b, x.b);
        a = a * (x.b / g) + x.a * (b / g);
        b = b / g * x.b;
        norm();
    }
};
void print(I x) {
    if (x >= 10)
        print(x / 10);
    cout << char('0' + x % 10);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    vector<int> in(n), q;
    vector<F> v(n);
    for (int i = 0; i < n; i++) {
        int d;
        cin >> d;
        g[i].resize(d);
        for (int &x : g[i]) {
            cin >> x;
            --x;
            in[x]++;
        }
        if (i < m)
            v[i].a = 1;
    }
    for (int i = 0; i < n; i++)
        if (!in[i])
            q.push_back(i);
    for (int i = 0; i < (int)q.size(); i++) {
        int u = q[i];
        if (g[u].empty())
            continue;
        F x = v[u];
        x.b *= g[u].size();
        x.norm();
        for (int w : g[u]) {
            v[w].add(x);
            if (!--in[w])
                q.push_back(w);
        }
    }
    for (int i = 0; i < n; i++)
        if (g[i].empty()) {
            print(v[i].a);
            cout << ' ';
            print(v[i].b);
            cout << "\n";
        }
}