#P18454. Information Spread

Information Spread

Information Spread

Ham 先生的班级有 nn 名学生,编号为 11 到 nn。一天,学生 11 得知了一条信息,随后学生们按照下述过程互相传播信息。

学生之间的关系用一张包含 nn 个顶点、mm 条边的有向图表示。每条边 (u,v,w)(u,v,w) 的权重 ww 是 [0,1][0,1] 内的实数。传播过程使用两个布尔数组:aware[u] 表示学生 uu 是否已经知道信息,visited[u] 表示其 DFS 是否已经开始过。

原题传播伪代码的完整含义如下:

SPREAD():
    将 aware[1..n] 全部初始化为 False
    将 visited[1..n] 全部初始化为 False
    aware[1] = True
    DFS(1)

DFS(u):
    如果 visited[u] 为 True:
        返回
    visited[u] = True
    按这些边在输入中出现的顺序,枚举从 u 出发的每条边 (u, v, w):
        如果 aware[u] 为 True 且 aware[v] 为 False:
            以概率 w 将 aware[v] 设为 True
        DFS(v)

每条边都是先尝试传播,再调用 DFS(v)。DFS(v) 的调用与传播是否发生、是否成功无关。即使 vv 已经被访问过,边上的传播条件仍须按伪代码检查;之后的 DFS 调用才因 visited[v] 返回。

请计算过程结束后,每名学生知道信息的概率,即最终 aware[i] 为 True 的概率。

输入格式

第一行包含两个整数 n,mn,m(3≤n≤1053\le n\le10^5,n−1≤m≤3×105n-1\le m\le3\times10^5)。

接下来 mm 行,每行包含四个整数 ui,vi,pi,qiu_i,v_i,p_i,q_i,表示从 uiu_i 指向 viv_i 的一条边,其权重为 wi=pi/qiw_i=p_i/q_i。其中:

  • 1≤ui,vi≤n1\le u_i,v_i\le n;
  • 0≤pi≤qi≤1050\le p_i\le q_i\le10^5,且 qi≠0q_i\ne0。

保证没有自环;任意有序点对 (i,j)(i,j) 至多有一条从 ii 到 jj 的边。保证所有顶点都能从顶点 11 到达,因而上述 DFS 会访问所有学生。边权可以为 00;这不会阻止 DFS 的调用。

输入只有一张图。

输出格式

输出 nn 行,第 ii 行包含一个整数,表示学生 ii 最终知道信息的概率对 M=998244353M=998244353 取模后的结果。

形式化地,若所求概率为有理数 p/qp/q,则输出 p⋅q−1 mod Mp\cdot q^{-1}\bmod M,其中 q−1q^{-1} 满足 qq−1≡1(modM)q q^{-1}\equiv1\pmod M。

样例 1

4 4
1 2 1 2
2 3 1 2
2 4 1 2
4 3 1 1
1
499122177
623902721
748683265

样例 2

6 12
1 2 81804 95651
2 3 39701 95895
2 4 6178 17992
3 5 72756 84510
5 6 40007 83640
2 6 60491 92219
5 3 37590 47735
4 5 6867 20289
4 3 75051 93231
6 5 48102 54448
6 1 40190 45274
1 5 37010 60312
1
947252499
124986918
535320090
929273289
551177734

样例说明

第一个样例中,学生 11 最开始知道信息。依次处理边 (1,2,1/2)(1,2,1/2)、(2,3,1/2)(2,3,1/2)、(2,4,1/2)(2,4,1/2) 和 (4,3,1)(4,3,1)。

学生 22 知道信息的概率为 1/21/2。学生 44 知道信息的概率为 (1/2)×(1/2)=1/4(1/2)\times(1/2)=1/4。

学生 33 最终仍不知道信息,有两种互斥情况:

  • 学生 22 没有得知信息;
  • 学生 22 已经得知信息,但处理 (2,3)(2,3) 和 (2,4)(2,4) 时均未成功传播。

因此,学生 33 最终知道信息的概率为

$$1-\frac12-\frac12\times\frac12\times\frac12=\frac38.$$