彻底搜索逆序对

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一个有 $N$ 个顶点的有向无环图。顶点 $i$ 有 $S_i$ 条出边；它的第 $j$ 条出边指向 $L_{i,j}$，边权为 $W_{i,j}\in\{0,1\}$。保证从顶点 $1$ 出发可以到达所有顶点。

初始有一个空数组 $Z$。定义函数：

void dfs(int i) {
    for (int j = 1; j <= S[i]; ++j) {
        Z.push_back(W[i][j]);
        dfs(L[i][j]);
    }
}

函数不会记录已经访问过的顶点，因此同一顶点可能被处理多次。

执行一次 $ exttt{dfs(1)}$后，$Z$ 只包含 $0$ 和 $1$。求 $Z$ 的逆序对数量，即满足 $x<y$ 且 $Z_x>Z_y$ 的下标对 $(x,y)$ 数量。答案对 $998244353$ 取模。

输入格式

第一行包含整数 $N$。

随后依次给出顶点 $1$ 到 $N$ 的信息。顶点 $i$ 的第一行包含整数 $S_i$；接下来的 $S_i$ 行，每行包含两个整数 $L_{i,j},W_{i,j}$，按输入顺序描述第 $j$ 条出边。

图中没有重边和有向环；从顶点 $1$ 可以到达所有顶点。

输出格式

输出 $Z$ 的逆序对数量对 $998244353$ 取模后的结果。

样例输入 1

5
2
4 0
3 1
0
1
2 0
2
3 1
5 1
0

样例输出 1

4

样例说明

执行过程如下图所示：

最终 $Z=[0,1,0,1,1,0]$，四个逆序对是 $(2,3),(2,6),(4,6),(5,6)$。

数据范围

• $2\le N\le10^5$；
• $0\le S_i\le N-1$；
• $1\le L_{i,j}\le N$；
• $W_{i,j}\in\{0,1\}$；
• $\sum S_i\le2\times10^5$。