思路与算法

考虑原树的线图：原来的每条边变成一个顶点，原顶点u关联的deg(u)条边在线图中构成一个团，团之间通过原边对应的顶点相连。在线图的DFS生成树中，每个团内部必须是一条哈密顿路径。固定一条起始边时，每个原顶点团的一端已定，其余deg−1个成员可任意排列，因此基础计数C=∏u(deg(u)−1)!。

令标记数为K。用容斥求“至少有一条标记可作根”。归并后只需扣除可见标记对：两条标记边之间的原树路径上不能有其他标记边。每对的归一化权值是其路径内部各原顶点1/(deg−1)的乘积，所有权重和记为S，答案C(K−S)。任意把原树定根，逆序汇总各子分支传来的最近标记质量。标记子边的质量直接为1，阻断更深标记；非标记子边使用孩子DP。顶点u的子分支质量两两相乘再乘w[u]=1/(deg−1)，加入S；若父边是标记，还临时补一个质量1的父分支用于本点配对。向父亲上传w[u]·子分支质量和，绝不上传临时父分支。全部DFS顺序迭代构建。

正确性说明

团内尚未访问的任意两点都相邻，所以DFS一旦进入团，就会沿未访问成员连续深入，生成哈密顿路径；团树结构使各团的排列独立。固定根边时，每团有(deg−1)!种排列，得到C。若要求两条标记a、b都能成为根，则它们之间每个团的两条路径边都必须是该团哈密顿路径的两个端点，局部排列数由(deg−1)!降为(deg−2)!，比例就是1/(deg−1)，其余团不变。三条及更多标记如果不共线，就无法同时满足某个团只有两个端点的要求，交集为空；若共线，交集仅由最外侧两条标记决定。

对某个最外侧标记对，假设中间有q条标记。容斥中该对及任意中间标记子集的系数总和为−(1−1)^q，因此q>0时完全相消，q=0时保留一次负号，恰是可见标记对。树上质量DP从每个方向只保留遇到的首条标记，标记边之后不再传递更深标记，所以不会计入不可见对。任意可见对在两分支会合处被唯一计算，分支质量与本点w相乘正好得到完整路径权重。S因此正确，乘基础计数后得到所有不同新树的并集大小。

复杂度

阶乘和1..100000的逆元一次线性预处理O(100000)时间、空间。每组建邻接表、父子顺序、逆序质量聚合均O(n)，输入标记O(K)，故总时间O(100000+Σn)，峰值空间O(100000+n)。包含最多T=10组各n=100000的范围，不依赖总n的额外假设。迭代遍历避免链形树的递归栈溢出。

易错点

计数对象是最终无向新树，不能直接把所有DFS顺序相加；同一新树可能允许多条标记作为起点。只有无中间标记的可见对保留扣项，不能减掉全部标记对。父标记分支只用于本点配对，不能再次上传造成重复计数。叶子的deg−1为0，但叶子不位于两条标记之间，DP可设其传递权为1，不能求0的逆元。模数为10^9+7而另一题2138是998244353，不要混用。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007, MAXN = 100000;
struct FastInput {
    static const int SZ = 1 << 16;
    char a[SZ];
    int at = 0, len = 0;
    int get() {
        if (at == len) {
            len = fread(a, 1, SZ, stdin);
            at = 0;
            if (!len)
                return -1;
        }
        return a[at++];
    }
    int next() {
        int c;
        do {
            c = get();
        } while (c <= 32 && c >= 0);
        int x = 0;
        while (c >= 48 && c <= 57) {
            x = x * 10 + c - 48;
            c = get();
        }
        return x;
    }
};
int main() {
    FastInput in;
    vector<long long> fac(MAXN + 1), inv(MAXN + 1);
    fac[0] = 1;
    for (int i = 1; i <= MAXN; ++i)
        fac[i] = fac[i - 1] * i % MOD;
    inv[1] = 1;
    for (int i = 2; i <= MAXN; ++i)
        inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    int type = in.next(), T = in.next();
    while (T--) {
        int n = in.next(), k = in.next();
        vector<vector<pair<int, int>>> g(n);
        for (int i = 0; i < n - 1; ++i) {
            int u = in.next() - 1, v = in.next() - 1;
            g[u].push_back({v, i});
            g[v].push_back({u, i});
        }
        vector<bool> mark(n - 1);
        for (int i = 0; i < k; ++i)
            mark[in.next() - 1] = true;
        vector<int> parent(n, -1), pe(n, -1), order;
        order.reserve(n);
        order.push_back(0);
        for (size_t i = 0; i < order.size(); ++i) {
            int u = order[i];
            for (auto e : g[u])
                if (e.first != parent[u]) {
                    parent[e.first] = u;
                    pe[e.first] = e.second;
                    order.push_back(e.first);
                }
        }
        long long C = 1, S = 0;
        for (int u = 0; u < n; ++u)
            C = C * fac[g[u].size() - 1] % MOD;
        vector<long long> dp(n);
        for (int i = n - 1; i >= 0; --i) {
            int u = order[i];
            long long sum = 0, pairs = 0;
            for (auto e : g[u])
                if (parent[e.first] == u) {
                    long long mass = mark[e.second] ? 1 : dp[e.first];
                    pairs = (pairs + sum * mass) % MOD;
                    sum += mass;
                    if (sum >= MOD)
                        sum -= MOD;
                }
            if (pe[u] >= 0 && mark[pe[u]]) {
                pairs += sum;
                if (pairs >= MOD)
                    pairs -= MOD;
            }
            long long w = g[u].size() > 1 ? inv[g[u].size() - 1] : 1;
            S = (S + pairs * w) % MOD;
            dp[u] = sum * w % MOD;
        }
        long long answer = C * ((k - S + MOD) % MOD) % MOD;
        printf("%lld\n", answer);
    }
}