#NOIP2024C. 树的遍历(traverse)民间数据

树的遍历(traverse)民间数据

[NOIP2024] 树的遍历(民间数据)

题目背景

1s 512MB

题目描述

小 Q 是一个算法竞赛初学者,正在学习图论知识中的树的遍历。一棵由 nn 个结点,n1n - 1 条边构成的树,初始时所有结点都未被标记,它的遍历过程如下:

  1. 选择一个结点 ss 作为遍历起始结点,并把该结点打上标记。
  2. 假设当前访问的结点为 uu,寻找任意一个与 uu 相邻且未标记的结点 vv,将 vv 作为新的当前访问结点并打上标记。之后再次进入第 22 步。
  3. 假设在第 22 步中,与 uu 相邻的结点都已被标记,如果 u=su = s 则遍历过程结束,否则将 uu 设为遍历 uu 之前的上一个结点并再进入第 22 步。

例如在下面的树中,一种可能的遍历过程如下:

  • 选取 11 作为遍历起始结点,并把 11 打上标记;
  • 2211 相邻且未标记,将 22 设为当前访问结点,并把 22 打上标记。
  • 2233 相邻且未标记,将 33 设为当前访问结点,并把 33 打上标记。
  • 33 所有相邻的结点都被标记,将当前访问结点设为遍历结点 33 之前的结点 22
  • 2244 相邻且未标记,将 44 设为当前访问结点,并把 44 打上标记。
  • 44 所有相邻的结点都被标记,将当前访问结点设为遍历结点 44 之前的结点 22
  • 22 所有相邻的结点都被标记,将当前访问结点设为遍历结点 22 之前的结点 11
  • 11 所有相邻的结点都被标记,且 11 是遍历起始结点,故遍历结束。

作为一个奇思妙想的学生,小 Q 在学习完上述知识后不满足于以结点为基础的遍历方式,于是开始研究以边为基础的遍历方式。定义两条边相邻,当且仅当它们有一个公共的结点。初始时,所有的边都未被标记。这种以边为基础的遍历过程如下:

  1. 选择一条边 bb 作为遍历起始边,并把该边打上标记。
  2. 假设当前访问边为 ee,寻找任意一条与 ee 相邻且未标记的边 ff,将 ff 作为新的当前访问边并打上标记。之后再次进入第 22 步。
  3. 假设在第 22 步中,与 ee 相邻的边都已被标记,如果 e=be = b 则遍历过程结束,否则将 ee 设为遍历 ee 之前的上一条边并再进入第 22 步。

例如在上面的树中,一种可能的遍历过程如下(定义 {u,v}\{u, v\} 表示连接结点 uuvv 的边):

  • 选取 {1,2}\{1, 2\} 作为遍历起始边,并把 {1,2}\{1, 2\} 打上标记;
  • {1,2}\{1, 2\}{2,3}\{2, 3\} 相邻且未标记,将 {2,3}\{2, 3\} 设为当前访问边,并把 {2,3}\{2, 3\} 打上标记。
  • {2,3}\{2, 3\}{2,4}\{2, 4\} 相邻且未标记,将 {2,4}\{2, 4\} 设为当前访问边,并把 {2,4}\{2, 4\} 打上标记。
  • {2,4}\{2, 4\} 所有相邻的边都被标记,将当前访问边设为遍历 {2,4}\{2, 4\} 之前的边 {2,3}\{2, 3\}
  • {2,3}\{2, 3\} 所有相邻的边都被标记,将当前访问边设为遍历 {2,3}\{2, 3\} 之前的边 {1,2}\{1, 2\}
  • {1,2}\{1, 2\} 所有相邻的边都被标记,且 {1,2}\{1, 2\} 是遍历起始边,故遍历结束。

小 Q 惊奇的发现,在这个新的树的遍历过程中,如果将每条边看作一个新的结点,将步骤 22 中的所有新结点 eeff 连接一条新边,就会生成一棵由 n1n-1 个新结点和 n2n-2 条新边连接成的新树。例如上述遍历过程得到的新树如下(新的结点和新边都用红色表示):

现在小 Q 在 n1n - 1 条边中选择了 kk 条关键边。小 Q 想知道,以任意一条关键边作为起始遍历边,通过上述遍历过程能够生成多少种不同的新树。这里两棵树被认为是不同的,当且仅当至少存在某一对新的结点,它们仅在其中一棵树中连有新边。

由于结果可能很大,你只需要输出其对 109+710^9+7 取模的结果即可。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 c,Tc, T,表示测试点的编号和测试数据的组数。在样例中,cc 表示该样例与测试点 cc 的数据范围相同。

接下来包含 TT 组数据,每组数据的格式如下:

  • 第一行包含两个整数 n,kn, k,表示树的结点数以及小 Q 选择的关键边的数量。
  • 接下来 n1n - 1 行,第 ii 行包含两个整数 ui,viu_i, v_i,表示树上编号为 ii 的边连接结点 uiu_iviv_i
  • 接下来一行包含 kk 个整数 e1,e2,,eke_1, e_2, \dots, e_k,表示小 Q 选择的关键边的编号。保证关键边的编号互不相同。

输出格式

对于每组测试数据输出一行,包含一个整数,表示结果对 109+710^9 + 7 取模的结果。

样例 #1

样例输入 #1

1 1
4 1
1 2
2 3
2 4
1

样例输出 #1

2

样例 #2

样例输入 #2

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

样例输出 #2

3

提示

【样例 1 解释】

两种可能的新树如下:

  • 新结点 {1,2}\{1, 2\} 和新结点 {2,3}\{2, 3\} 连新边,新结点 {2,3}\{2, 3\} 和新结点 {2,4}\{2, 4\} 连新边。
  • 新结点 {1,2}\{1, 2\} 和新结点 {2,4}\{2, 4\} 连新边,新结点 {2,4}\{2, 4\} 和新结点 {2,3}\{2, 3\} 连新边。

【样例 2 解释】

三种可能的新树如下:

  • 新结点 {1,2}\{1, 2\}{1,3}\{1, 3\}{1,2}\{1, 2\}{2,4}\{2, 4\}{2,4}\{2, 4\}{2,5}\{2, 5\} 之间分别连新边。该新树可以选择 {1,2}\{1, 2\} 作为起始遍历边得到。
  • 新结点 {1,2}\{1, 2\}{1,3}\{1, 3\}{1,2}\{1, 2\}{2,5}\{2, 5\}{2,5}\{2, 5\}{2,4}\{2, 4\} 之间分别连新边。该新树可以选择 {1,2}\{1, 2\}{2,4}\{2, 4\} 作为起始遍历边得到。
  • 新结点 {1,2}\{1, 2\}{1,3}\{1, 3\}{1,2}\{1, 2\}{2,4}\{2, 4\}{1,2}\{1, 2\}{2,5}\{2, 5\} 之间分别连新边。该新树可以选择 {2,4}\{2, 4\} 作为起始遍历边得到。

【样例 3】

见附件的 traverse/traverse3.in 与 traverse/traverse3.ans。

该组样例满足 c=4c = 4

【样例 4】

见附件的 traverse/traverse4.in 与 traverse/traverse4.ans。

该组样例满足 c=7c = 7

【样例 5】

见附件的 traverse/traverse5.in 与 traverse/traverse5.ans。

该组样例满足 c=11c = 11

【样例 6】

见附件的 traverse/traverse6.in 与 traverse/traverse6.ans。

该组样例满足 c=13c = 13

【样例 7】

见附件的 traverse/traverse7.in 与 traverse/traverse7.ans。

该组样例满足 c=15c = 15

【样例 8】

见附件的 traverse/traverse8.in 与 traverse/traverse8.ans。

该组样例满足 c=16c = 16

【样例 9】

见附件的 traverse/traverse9.in 与 traverse/traverse9.ans。

该组样例满足 c=18c = 18

【样例 10】

见附件的 traverse/traverse10.in 与 traverse/traverse10.ans。

该组样例满足 c=19c = 19

【样例 11】

见附件的 traverse/traverse11.in 与 traverse/traverse11.ans。

该组样例满足 c=22c = 22

【样例 12】

见附件的 traverse/traverse12.in 与 traverse/traverse12.ans。

该组样例满足 c=24c = 24

【数据范围】

对于所有的测试数据,保证:

  • 1T101 \leq T \leq 10
  • 2n1052 \leq n \leq 10^5
  • 1k<n1 \leq k < n
  • 对于任意的 i(1in1)i(1 \leq i \leq n - 1),都有 1ui,vin1 \leq u_i, v_i \leq n,且构成一颗合法的树。
  • 对于任意的 i(1ik)i(1 \leq i \leq k),都有 1ei<n1 \leq e_i < n,且两两不同。
测试点编号 nn kk 特殊性质
131\sim 3 5\leq 5 1\leq 1
464\sim 6 105\leq 10^5
7107\sim 10 2\leq 2
11,1211,12 500\leq 500 8\leq 8
13,1413,14 102\leq 10^2 <n<n
1515 500\leq 500
16,1716,17 105\leq 10^5 500\leq 500
1818 <n<n A
192119\sim 21 B
22,2322,23 2×104\leq 2\times 10^4
24,2524,25 105\leq 10^5
  • 特殊性质 A:对于任意的 i(1in1)i(1 \leq i \leq n - 1),都有 ui=i,vi=i+1u_i = i, v_i = i + 1
  • 特殊性质 B:对于任意的 i(1in1)i(1 \leq i \leq n - 1),都有 ui=1,vi=i+1u_i = 1, v_i = i + 1

【提示】

数据输入的规模可能较大,请选手注意输入读取方式的效率。