首页 > 试题广场 >

简单

[编程题]简单
给定一个森林，每个点都有一定概率会消失，一条 的边存在的条件是，u 存在且 v 存在。
有若干次询问，每次给定 [l,r]，然后把下标不在 [l,r] 的点都删掉后，问剩余点和所有边构成的图的连通块个数的期望。
注意每次删除的意思是只在当前这个询问的时候删除，对于其它询问互相独立

输入描述:
第一行三个整数 n,m,q，分别表示点的个数和边的个数和询问次数。
之后 n 行，第 i+1 行有两个整数 ai,bi，表示第 i 个点存在的概率是  。
之后 m 行，每行有两个整数 u,v，表示存在一条连接 u 和 v 的边，保证无重边无自环。
之后 q 行，每行两个整数 [l,r]，表示一次询问。


输出描述:
对于每一次询问，输出一行一个整数表示答案，输出对 109+7 取模。
示例1

输入

2 1 1
1 1
1 1
1 2
1 2

输出

1

说明

一共就俩点，都一定存在，所以连接它们的这条边一定存在，所以这俩点构成的图的连通块个数一定是 1
示例2

输入

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

输出

2
333333337
666666673
2
333333337
示例3

输入

10 9 10
2922 17409
11774 17075
4095 19350
5213 7090
21155 26703
9167 16671
257 1197
201 308
13874 27985
12034 32560
1 6
1 9
6 5
6 4
1 10
4 3
4 2
10 7
6 8
2 3
3 9
1 3
2 2
2 6
3 5
2 2
3 5
5 8
4 4

输出

613369885
419229271
380731593
15695462
543771231
562072744
15695462
562072744
891100707
526234137

说明

（以下内容与本题无关）

这个样例，无疑是善良的出题人无私的馈赠。

大量精心构造的 n ≤ 100,m ≤ 200 的测试数据，涵盖了测试点中所有出现性质的组合。

你可以利用这个测试点，对自己的程序进行全面的检查。

足量的数据组数、不大的数据范围和多种多样的数据类型，能让程序中的错误无处遁形。

出题人相信，这个美妙的样例，可以给拼搏于 AC 这道题的逐梦之路上的你，提供一个有力的援助。

备注:
对于  的数据，保证 n = 10 。
对于另外  的数据，保证 q=1 。
对于所有  的数据，保证 1 ≤ n,q ≤ 105,0 ≤ m < n,1 ≤ ai ≤ bi ≤ 105 。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

枚举 数学
难度：
0条回答 8浏览

热门推荐

相关试题

简单

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号