#P9480. [NOI2023] 深搜

[NOI2023] 深搜

题目描述

深度优先搜索是一种常见的搜索算法。通过此算法,我们可以从一个无重边、无自环的无向连通图 G=(V,E)G = (V, E),和某个出发点 ss,得到一棵树 TT

算法的流程描述如下:

  1. 将栈 SS 设置为空,并令 T=(V,)T = (V, \emptyset),即 TT 的边集初始为空。
  2. 首先将出发点 ss 压入 SS 中。
  3. 访问栈顶节点 uu,并将 uu 标记为“已访问的”。
  4. 如果存在与 uu 相邻且未被访问的节点,则任意地从这些节点中挑选一个记为 vv。我们将边 (u,v)(u, v) 加入 TT 的边集中,并将 vv 压入栈 SS 中,然后回到步骤 3。若不存在这样的节点,则从栈中弹出节点 uu

可以证明,当图 GG 为连通图时,该算法会得到图的某一棵生成树 TT。但算法得到的树 TT 可能不是唯一的,它取决于搜索的顺序,也就是算法的第 4 步所选取的顶点。指定出发点 ss 后,如果能够选取一种特定的搜索顺序,使得算法得到的树恰好是 TT,则我们称 TTGG 的一棵 ss-dfs 树

现在给定一棵 nn 个顶点的树 TT,顶点编号为 1n1 \sim n,并额外给出 mm 条边。我们保证这 mm 条边两两不同,连接不同的顶点,且与 TT 中的 n1n - 1 条树边两两不同。我们称额外给出的 mm 条边为非树边。在这 nn 个顶点中,我们指定了恰好 kk 个顶点作为关键点

现在你想知道,有多少种选取这 mm 条非树边的方法(可以全部不选),使得:将 TT 的边与被选中的非树边构成图 GG 之后,存在某个关键点 ss,使得 TTGG 的一棵 ss-dfs 树。

由于答案可能十分巨大,你只需要输出方案数在模 (109+7)(10 ^ 9 + 7) 意义下的值。

输入格式

输入的第一行包含一个整数 cc,表示测试点编号。c=0c = 0 表示该测试点为样例。

输入的第二行包含三个正整数 n,m,kn, m, k,分别表示顶点个数,非树边的数量,关键点的数量。

接下来 n1n - 1 行,每行包含两个正整数 u,vu, v 表示树 TT 的一条边。保证这 n1n - 1 条边构成了一棵树。

接下来 mm 行,每行包含两个正整数 a,ba, b 表示一条非树边。保证 (a,b)(a, b) 不与树上的边重合,且没有重边。

输入的最后一行包含 kk 个正整数 s1,s2,,sks_1, s_2, \dots, s_k,表示 kk 个关键点的编号。保证 s1,s2,,sks_1, s_2, \dots, s_k 互不相同。

输出格式

输出一行包含一个非负整数,表示方案数在模 (109+7)(10 ^ 9 + 7) 意义下的值。

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

3

见附件中的 dfs/dfs2.in。
见附件中的 dfs/dfs2.ans。
见附件中的 dfs/dfs3.in。
见附件中的 dfs/dfs3.ans。
见附件中的 dfs/dfs4.in。
见附件中的 dfs/dfs4.ans。
见附件中的 dfs/dfs5.in。
见附件中的 dfs/dfs5.ans。
见附件中的 dfs/dfs6.in。
见附件中的 dfs/dfs6.ans。

提示

【样例解释 #1】

在这个样例中,有三种选取非树边的方法:只选取边 (1,3)(1, 3),只选取边 (2,4)(2, 4),或不选取任何条非树边。

如果只选取边 (1,3)(1, 3),或者不选取任何一条非树边,则我们发现 TT 都是图 GG33-dfs 树。指定的搜索顺序如下:

  1. 33 放入栈 SS 中。此时 S=[3]S = [3]
  2. 33 标记为“已访问的”。
  3. 由于 3322 相连,且 22 是“未访问的”,将 22 放入栈 SS 中,并将 (3,2)(3, 2) 加入树 TT 中,此时 S=[3,2]S = [3, 2]
  4. 22 标记为“已访问的”。
  5. 由于 2211 相连,且 11 是“未访问的”,将 11 放入栈 SS 中,并将 (2,1)(2, 1) 加入树 TT 中,此时 S=[3,2,1]S = [3, 2, 1]
  6. 由于与 11 相邻的点都是“已访问的”,将 11 弹出栈,此时 S=[3,2]S = [3, 2]
  7. 由于与 22 相邻的点都是“已访问的”,将 22 弹出栈,此时 S=[3]S = [3]
  8. 由于 3344 相连,且 44 是“未访问的”,将 44 放入栈 SS 中,并将 (3,4)(3, 4) 加入树 TT 中,此时 S=[3,4]S = [3, 4]
  9. 由于与 44 相连的点都是“已访问的”,将 44 弹出栈,此时 S=[3]S = [3]
  10. 由于与 33 相连的点都是“己访问的”,将 33 弹出栈,此时 SS重新变为空。

如果只选取边 (2,4)(2, 4),则我们可以说明 TT 是图 GG22-dfs 树。指定的搜索顺序如下:

  1. 22 放入栈 SS 中。此时 S=[2]S = [2]
  2. 22 标记为“已访问的”。
  3. 由于 2233 相连,且 33 是“未访问的”,将 33 放入栈 SS 中,并将 (2,3)(2, 3) 加入树 TT 中,此时 S=[2,3]S = [2, 3]
  4. 33 标记为“已访问的”。
  5. 由于 3344 相连,且 44 是“未访问的”,将 44 放入栈 SS 中,并将 (3,4)(3, 4) 加入树 TT 中,此时 S=[2,3,4]S = [2, 3, 4]
  6. 由于与 44 相邻的点都是“己访问的”,将 44 弹出栈,此时 S=[2,3]S = [2, 3]
  7. 由于与 33 相邻的点都是“已访问的”,将 33 弹出栈,此时 S=[2]S= [2]
  8. 由于 2211 相连,且 11 是“未访问的”,将 11 放入栈 SS 中,并将 (2,1)(2, 1) 加入树 TT 中,此时 S=[2,1]S = [2, 1]
  9. 由于与 11 相连的点都是“已访问的”,将 11 弹出栈此时 S=[2]S = [2]
  10. 由于与 22 相连的点都是“已访问的”,将 22 弹出栈,此时 SS 重新变为空。

【样例解释 #2】

这个样例满足测试点 464 \sim 6 的约束条件。

【样例解释 #3】

这个样例满足测试点 101110 \sim 11 的约束条件。

【样例解释 #4】

这个样例满足测试点 121312 \sim 13 的约束条件。

【样例解释 #5】

这个样例满足测试点 141614 \sim 16 的约束条件。

【样例解释 #6】

这个样例满足测试点 232423 \sim 24 的约束条件。

【数据范围】

对于所有测试数据保证:1kn5×1051 \le k \le n \le 5 \times 10 ^ 51m5×1051 \le m \le 5 \times 10 ^ 5

测试点编号 nn \le mm \le kk \le 特殊性质
131 \sim 3 66 nn
464 \sim 6 1515 66
797 \sim 9 300300
101110 \sim 11 nn A
121312 \sim 13 B
141614 \sim 16
171817 \sim 18 2×1052 \times 10 ^ 5 A
192119 \sim 21 B
2222
232523 \sim 25 5×1055 \times 10 ^ 5

特殊性质 A:保证在 TT 中,ii 号点与 i+1i + 1 号点相连(1i<n1 \le i < n)。

特殊性质 B:保证若将 TT 的边与所有 mm 条非树边构成一个图 GG,则 TTGG 的棵 11-dfs 树。

请注意,11 号点不一定是 kk 个关键点之一。