一、题意理解

题目定义了一种基于边的遍历方式，过程类似于 DFS 回溯。
初始时选择一条边 $b$ 作为起点，标记它，然后不断找相邻的未标记边进行递归遍历，回溯时回到上一条边。
遍历结束后，把每条边看作新图的结点，遍历过程中每次访问新边 $f$ 时，就在新图中连接 $e \to f$（$e$ 是当前边，$f$ 是下一步访问的边），这样会形成一棵新树，结点数为 $n-1$，边数为 $n-2$。

题目要求：
给定原树和 $k$ 条关键边，若以任意一条关键边作为起始遍历边，能生成多少种不同的新树（新树不同指边集不同）。
输出对 $10^9+7$ 取模的结果。

二、问题转化

原树有 $n-1$ 条边，新树也有 $n-1$ 个结点（对应原树的边）。
新树的边是在遍历过程中“访问顺序”中相邻的边之间建立的。

实际上，这种遍历过程等价于在原树的线图（line graph） 上做 DFS，线图的结点是原树的边，线图的边表示原树的两条边有公共结点。
原树是树，所以它的线图也是树（因为树是二分图，且线图是弦图，但这里简单来说，原树 $T$ 的线图 $L(T)$ 仍是树当且仅当 $T$ 是星图？不对，这里要小心）。

其实原树 $T$ 的线图 $L(T)$ 是树吗？

• 原树 $T$ 的线图定义：结点是 $T$ 的边，若两条边在 $T$ 中有公共结点，则在线图中连边。
• 对于 $T$ 是路径 $P_n$，$L(T)$ 是路径 $P_{n-1}$，仍是树。
• 对于 $T$ 是星图 $K_{1,n-1}$，$L(T)$ 是完全图 $K_{n-1}$，不是树。
• 对于一般树，$L(T)$ 是连通图，但不是树（因为可能有环，比如星图的情况）。
  但题目中，遍历是在原树的边上进行，但新树的边是遍历顺序决定的，不是线图的所有边，而是遍历 DFS 树。

所以问题变成：
在原树的线图上，以某条关键边为根，做 DFS 遍历，DFS 树有多少种可能？
但 DFS 树的数量与根有关，并且题目要求：只要某棵 DFS 树能被某个关键边作为根生成，就计入一次，但不同关键边可能生成同一棵 DFS 树，这时只算一次。

三、样例分析

样例 1：
原树：1-2, 2-3, 2-4
关键边：1（即 1-2 这条边）
从 1-2 出发，可能的 DFS 顺序：

• 1-2 → 2-3 → 2-4
  新树： (1-2)-(2-3), (2-3)-(2-4)
• 1-2 → 2-4 → 2-3
  新树： (1-2)-(2-4), (2-4)-(2-3)

两种新树不同，所以输出 2。

四、算法核心

经过分析（参考官方题解或已知 AC 代码），这个问题可以转化为树上概率期望计数问题。

我们考虑：
新树的形态由遍历时每一步选择相邻未访问边的顺序决定。
每一步，当前边 $e$ 连接的两个端点中，有一个是“来自上一条边的结点”，另一个是“新结点”。
从当前边出发，可选的相邻未访问边是新结点所连的其他边（除了当前边）。

设 $deg[u]$ 表示结点 $u$ 的度数。
当遍历到一条边 $(u,v)$，且是从 $u$ 方向来的，那么下一步可选的是 $v$ 的其他邻边（除了 $(u,v)$ 本身）。
选择顺序任意，所以对于度数为 $d$ 的结点，其邻边的访问顺序有 $(d-1)!$ 种。

关键结论（已知解法）

1. 把原树看作无根树，每条边有两个方向，分别计算概率。
2. 定义 $dp[u][0/1]$ 表示在 $u$ 的父边（来自父节点方向）是否关键边时，子树的方案数相关值。
3. 最终答案与每个结点的度数阶乘有关，并且要计算所有关键边作根时的总方案数，可以一次树形 DP 完成。

从代码看：

• sum[u][0] 表示从 $u$ 出发，父边不是关键边的“方案概率”或“方案数”。
• sum[u][1] 表示从 $u$ 出发，父边是关键边的“方案概率”或“方案数”。
• 在 DFS 中，合并子树时，如果子结点 $v$ 的边是关键边，则 sum[v][1] += sum[v][0]; sum[v][0] = 0，即关键边必须作为访问入口。
• 然后计算 val 来累加不同子树之间的路径贡献。
• 最后乘以 fac[deg[i]]，因为每个结点处边的顺序可任意排列。

五、代码流程

1. 预处理阶乘和逆元。
2. 读入树和关键边标记。
3. 特判 $n=2$ 时答案为 1。
4. 建图，记录每条边是否关键边。
5. 选一个非叶子结点作根（度数 > 0）。
6. 树形 DP：
   • 对于结点 $u$，枚举子结点 $v$，根据 $(u,v)$ 是否关键边调整 $sum[v]$。
   • 计算子树间产生的路径贡献 s。
   • 按度数倒数归一化（概率视角）。
7. 最后 s * ∏ fac[deg[i]] 得到答案。

六、算法标签

• 树形 DP
• 概率与期望
• 组合数学
• DFS 树计数
• 模运算

七、总结

这道题的核心是把“边遍历生成新树”的方案数，通过树形 DP 和组合计数，转化为每个结点处邻边排列的乘积，并利用概率归一化来简化计算。
最终用一次 DFS 统计所有关键边作根的总方案数，避免了分别枚举每个关键边作根的重复计算。