记录编号	613922	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[USACO26 FEB G]Random Tree Generation	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	3.399 s
提交时间	2026-04-02 15:38:19	内存使用	9.46 MiB

#include <cstring>
#include <iostream>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
int hd[N], nxt[N * 2], to[N * 2], num = 1;
void add(int u, int v) {
    num++;
    to[num] = v;
    nxt[num] = hd[u];
    hd[u] = num;
}
int sz[N];
void dfs(int u, int fa) {
    sz[u] = 1;
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
long long fpow(long long x, long long y) {
    long long res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
int n;
long long f[N];
void dfs2(int u, int fa) {
    for (int i = hd[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        f[v] = f[u] * sz[v] % mod * fpow(n - sz[v], mod - 2) % mod;
        dfs2(v, u);
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        num = 1;
        memset(hd, 0, sizeof(hd));
        for (int i = 1; i <= n - 1; i++) {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        dfs(1, 0);
        long long fz = 1;  // 分子
        for (int i = 1; i <= n; i++) {
            fz = fz * i % mod;
        }
        long long fm = 1;  // 分母
        for (int i = 1; i <= n; i++) {
            fm = fm * sz[i] % mod;
        }
        f[1] = fz * fpow(fm, mod - 2) % mod;
        dfs2(1, 0);
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += f[i];
            ans %= mod;
        }
        fm = 1;
        for (int i = 1; i <= n - 1; i++) fm = fm * i % mod;
        for (int i = 1; i <= n; i++) fm = fm * i % mod;
        cout << ans * fpow(fm, mod - 2) % mod << endl;
    }
    return 0;
}