#P6916. duliu
duliu
Problem C. 点独立集(duliu)
时间限制:3s;空间限制:1024MB。
题目描述
给定一张连通无向图,满足每条边最多在一个点简单环上。再给出它的一个点独立集,求字典序小于该点独立集的非空点独立集数量。
点独立集指任意两点间都没有边相连的点集。将集合 分别按升序排成序列 ,设最长公共前缀的长度为 。当且仅当以下任一条件成立,称 的字典序小于 :
- 且 ;
- 且 ,并且 。
答案对 取模后输出。保证没有自环,但可能有重边。
输入格式
从标准输入读入。第一行三个正整数 ,分别为图的点数、边数、给定独立集的大小。
接下来 行,每行两个正整数 ,表示连接点 的一条边。之后一行有 个互不相同的正整数,表示给定独立集中的点。
输出格式
向标准输出写出一个整数,表示答案对 取模后的值。
样例 1
4 3 2
1 2
2 3
3 4
2 4
4
四个独立集为 、、、。
样例二、三
见原题下发文件 ex_duliu2.in、ex_duliu2.out,以及 ex_duliu3.in、ex_duliu3.out。
限制与约定
记每条边所在点简单环的最大数量为 。所有测试点满足 ,。
| 测试点编号 | 特殊性质 | ||
|---|---|---|---|
| 1 | 5 | 0 | 无 |
| 2 | 10 | ||
| 3 | 15 | ||
| 4 | 20 | ||
| 5—7 | 1000 | ||
| 8—10 | 1 | ||
| 11—13 | 1000000 | 0 | 第 条边连接点 和点 |
| 14—15 | 100000 | 无 | |
| 16 | 300000 | ||
| 17 | 1000000 | ||
| 18—20 | 100000 | 1 | |
| 21—22 | 300000 | ||
| 23 | 500000 | ||
| 24—25 | 1000000 |