← 返回题目列表

Codeforces · 1866/C

C. 完全寻找反转

中文机器翻译题面 查看原题

Pak Chanek 有一个有向无环图(没有任何循环的有向图),其中包含 $$$N$$$ 个顶点。顶点 $$$i$$$ 具有远离该顶点的 $$$S_i$$$ 边。顶点 $$$i$$$ 的第 $$$j$$$ 条边指向顶点 $$$L_{i,j}$$$,并且具有整数 $$$W_{i,j}$$$ ($$$0\leq W_{i,j}\leq1$$$)。关于图的另一个信息是,图的形状使得每个顶点都可以从顶点 $$$1$$$ 通过零个或多个有向边到达。

Pak Chanek 有一个数组 $$$Z$$$ 最初为空。

Pak Chanek 定义函数 dfs 如下:

请注意,该函数不会跟踪哪些顶点已被访问,因此每个顶点可以被处理多次。

假设 Pak Chanek 执行了 dfs(1) 一次。之后,Pak Chanek 将得到一个数组 $$$Z$$$,其中包含一些元素 $$$0$$$ 或 $$$1$$$。将数组 $$$Z$$$ 中的反转定义为一对索引 $$$(x, y)$$$ ($$$x < y$$$),使得 $$$Z_x > Z_y$$$。如果 Pak Chanek 执行 dfs(1) 一次,$$$Z$$$ 中有多少种不同的反转?由于答案可能非常大,因此输出对 $$$998\,244\,353$$$ 取模的答案。

输入

第一行包含一个整数 $$$N$$$ ($$$2 \leq N \leq 10^5$$$) — 图中的顶点数。以下行包含从顶点 $$$1$$$ 到顶点 $$$N$$$ 的每个顶点的描述。

每个顶点 $$$i$$$ 的第一行包含一个整数 $$$S_i$$$ ($$$0 \leq S_i \leq N-1$$$) — 远离顶点 $$$i$$$ 的边数。

每个顶点 $$$i$$$ 的接下来 $$$S_i$$$ 行的第 $$$j$$$ 包含两个整数 $$$L_{i,j}$$$ 和 $$$W_{i,j}$$$ ($$$1 \leq L_{i,j} \leq N$$$; $$$0 \leq W_{i,j} \leq 1$$$) — 一条远离顶点 $$$i$$$ 的边,指向顶点 $$$L_{i,j}$$$,并且具有整数 $$$W_{i,j}$$$。对于每个 $$$i$$$,$$$L_{i,1}$$$、$$$L_{i,2}$$$、...、$$$L_{i,S_i}$$$ 的值是成对不同的。

保证所有顶点的 $$$S_i$$$ 之和不超过 $$$2 \cdot 10^5$$$。图中没有循环。每个顶点都可以从顶点 $$$1$$$ 通过零个或多个有向边到达。

输出

一个整数,表示 Pak Chanek 执行 dfs(1) 一次时 $$$Z$$$ 中的反转次数。由于答案可能非常大,因此输出对 $$$998\,244\,353$$$ 取模的答案。

示例

输入 #1

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

输出 #1

4

注意

下面是图上的dfs(1)过程。

最后,$$$Z=[0,1,0,1,1,0]$$$。它的所有反转都是 $$$(2,3)$$$、$$$(2,6)$$$、$$$(4,6)$$$ 和 $$$(5,6)$$$。