Completely Searching for Inversions
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1900
Tags: dfs and similar, dp, graphs

Pak Chanek has a directed acyclic graph (a directed graph that does not have any cycles) containing $$$N$$$ vertices. Vertex $$$i$$$ has $$$S_i$$$ edges directed away from that vertex. The $$$j$$$-th edge of vertex $$$i$$$ that is directed away from it, is directed towards vertex $$$L_{i,j}$$$ and has an integer $$$W_{i,j}$$$ ($$$0\leq W_{i,j}\leq1$$$). Another information about the graph is that the graph is shaped in such a way such that each vertex can be reached from vertex $$$1$$$ via zero or more directed edges.

Pak Chanek has an array $$$Z$$$ that is initially empty.

Pak Chanek defines the function dfs as follows:

Note that the function does not keep track of which vertices have been visited, so each vertex can be processed more than once.

Let's say Pak Chanek does dfs(1) once. After that, Pak Chanek will get an array $$$Z$$$ containing some elements $$$0$$$ or $$$1$$$. Define an inversion in array $$$Z$$$ as a pair of indices $$$(x, y)$$$ ($$$x < y$$$) such that $$$Z_x > Z_y$$$. How many different inversions in $$$Z$$$ are there if Pak Chanek does dfs(1) once? Since the answer can be very big, output the answer modulo $$$998\,244\,353$$$.

Input format:
The first line contains a single integer $$$N$$$ ($$$2 \leq N \leq 10^5$$$) — the number of vertices in the graph. The following lines contain the description of each vertex from vertex $$$1$$$ to vertex $$$N$$$.

The first line of each vertex $$$i$$$ contains a single integer $$$S_i$$$ ($$$0 \leq S_i \leq N-1$$$) — the number of edges directed away from vertex $$$i$$$.

The $$$j$$$-th of the next $$$S_i$$$ lines of each vertex $$$i$$$ contains two integers $$$L_{i,j}$$$ and $$$W_{i,j}$$$ ($$$1 \leq L_{i,j} \leq N$$$; $$$0 \leq W_{i,j} \leq 1$$$) — an edge directed away from vertex $$$i$$$ that is directed towards vertex $$$L_{i,j}$$$ and has an integer $$$W_{i,j}$$$. For each $$$i$$$, the values of $$$L_{i,1}$$$, $$$L_{i,2}$$$, ..., $$$L_{i,S_i}$$$ are pairwise distinct.

It is guaranteed that the sum of $$$S_i$$$ over all vertices does not exceed $$$2 \cdot 10^5$$$. There are no cycles in the graph. Each vertex can be reached from vertex $$$1$$$ via zero or more directed edges.

Output format:
An integer representing the number of inversions in $$$Z$$$ if Pak Chanek does dfs(1) once. Since the answer can be very big, output the answer modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
The following is the dfs(1) process on the graph.

In the end, $$$Z=[0,1,0,1,1,0]$$$. All of its inversions are $$$(2,3)$$$, $$$(2,6)$$$, $$$(4,6)$$$, and $$$(5,6)$$$.

Example input:
5
2
4 0
3 1
0
1
2 0
2
3 1
5 1
0

Example output:
4

Editorial:
Note that during the entire process, each time we do dfs(x) for the same value of $$$x$$$, the sequence of values appended to the end of $$$Z$$$ is always the same. So, for each vertex $$$x$$$, we want to obtain some properties about the sequence of values that will be appended if we do dfs(x). Since we want to calculate the number of inversions in a sequence of $$$0$$$ and $$$1$$$ elements, for each $$$x$$$, we want to calculate:
• $$$f_0[x]$$$: the number of $$$0$$$ elements appended.
• $$$f_1[x]$$$: the number of $$$1$$$ elements appended.
• $$$\text{inv}[x]$$$: the number of inversions completely within the sequence appended.
Then, we can solve the problem using dynamic programming on directed acyclic graph. For a vertex $$$x$$$, we iterate each vertex $$$y$$$ that it is directed towards (following the order given in the input). If the integer in the current edge is $$$w$$$, then we temporarily add $$$f_w[y]$$$ by $$$1$$$ and if $$$w=1$$$, then we temporarily add $$$\text{inv}[y]$$$ by $$$f_0[y]$$$. Then, we do the following transitions:
• Add $$$\text{inv}[x]$$$ by $$$\text{inv}[y]+f_1(x)\times f_0(y)$$$.
• Add $$$f_0[x]$$$ by $$$f_0[y]$$$.
• Add $$$f_1[x]$$$ by $$$f_1[y]$$$.
The answer is $$$\text{inv}[1]$$$.
Time complexity: $$$O(N+\sum S)$$$