问题 6667 --图上逆序数对

6667: 图上逆序数对

时间限制: 2 Sec  内存限制: 512 MB
提交: 2  解决: 2
[提交][状态][命题人:]

题目描述

给定一个包含 n 个点的有向无环图,每条边的边权值为 0 或 1 。
现在有一个空向量 V ,假设从节点 1 开始进行以下dfs操作:

// 从节点 i 为开始进行 dfs
void dfs(int i) {
    // 遍历节点 i 的每条出边
    for(int j = 1; j <= S[i]; j++) {
        V.push_back(B[i][j]); // 将当前边边 B[i][j] 加入向量 V 的末尾
        dfs(A[i][j]); // dfs递归后继节点A[i][j]
    }
}

在上述dfs操作结束后,向量 V 内会添加许多元素,求向量 V 的逆序数对数。
由于向量 V 可能包含很多元素,导致逆序数对数十分多,因此只需输出答案对 998244353 取模结果即可。

逆序对的定义请参考 https://baike.baidu.com/item/逆序对

输入

第一行包含一个正整数 n (2≤n≤10^5) ,表示图上节点数。
接下来有 n 组数据,第 i 组表示第 i 个节点的出边情况。
第 i 组里第一行包含一个整数 s[i] (0≤s[i]≤n-1) ,表示节点 i 的出边数量。
第 i 组里接下来 s[i] 行,每行包含两个整数 a[i][j],b[i][j] (1≤a[i][j]≤n, 0≤b[i][j]≤1) ,表示有一条有向边从节点 i 连向节点 a[i][j] ,权值为 b[i][j] 。

保证 s[i] 之和不超过 2·10^5 。
保证图中不存在环,从节点 1 开始可以访问到所有节点。

输出

输出有一个整数,表示答案对 998244353 取模的结果。
样例输入
Copy
5
2
4 0
3 1
0
1
2 0
2
3 1
5 1
0
样例输出
Copy
4

提示

样例解释:
样例描述的图如下所示:


从节点 1 开始执行 dfs(1) 后,得到向量 V=[0,1,0,1,1,0] ,该序列的逆序对数为 4 。

来源

[提交][状态]